~EEE
TRANSACTIONS ON
INFORMATION
THEORY,
VOI..
36,
NO.
5,
SF.PTEMRER
1990
96
1
The Wavelet Transform, Time-Frequency
Localization and Signal Analysis
Abstract
--Two
different procedures are studied by which a frequency
analysis
of
a time-dependent signal can
be
effected, locally in time. The
first procedure is the short-time
or
windowed Fourier transform, the
second is the “wavelet transform,” in which high frequency components
are studied with sharper time resolution than low frequency compo-
nents. The similarities and the differences between these two methods
are discussed. For both schemes a detailed study is made
of
the
reconstruction method and its stability, as a function of the chosen
time-frequency density. Finally the notion
of
“time-frequency localiza-
tion” is made precise, within this framework, by two localization theo-
rems.
I.
INTRODUCTION
A.
The Windowed Fourier Transform and Coherent States
N SIGNAL ANALYSIS one often encounters the
so-
I
called short-time Fourier transform, or windowed
Fourier transform. This consists of multiplying the signal
f(t)
with a usually compactly supported window function
g,
centered around
0,
and of computing the Fourier
coefficients of the product
gf.
These coefficients give an
indication of the frequency content of the signal
f
in a
neighborhood of
t
=
0.
This procedure is then repeated
with translated versions
of
the window function (i.e.,
g(t)
is replaced by
g(t
+
to),
g(t
+2t,,);
.
e,
where
t,,
is a
suitably chosen time translation step). This results in a
collection of Fourier coefficients
c,,,(
f)
=
/r
dteimoll’g(
t
-
nt,,)
f
(t)
-m
(rn,nEZ).
(1.1)
Similar coefficients also occur in a transform first pro-
posed by Gabor [l] for data transmission. The original
proposal used a Gaussian function
g,
and parameters
wO,
to
such that
wo.t,,
=
2~. A Gaussian window function is,
of course, not compactly supported, but it has many other
qualities. One
of
these
is
that it is the function which is
optimally concentrated in both time and frequency, and
therefore well-suited for an analysis in which both time
and frequency localization are important. Gabor’s original
proposal, with
wO.to
=
2~,
leads to unstable reconstruc-
Manuscript received November
9,
1987; revised December
7,
1988.
This work was presented in part at the International Conference on
Mathematical Physics, Marseille, France, July 1986.
The author was with the Mathematics Department, University
of
Michigan, Ann Arbor, MI 48109-1003. She
is
now with AT&T Bell
Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974.
IEEE
Log
Number 9036002.
tion (see
[2],
[3]; we shall come back to this in Section
11-C-1). The Gabor functions have been used in many
different settings in signal analysis, either in discrete
lattices (with
~~.t~)
<
27-r
for stable reconstruction)
or
in
the continuous form described next.
In
many
of
these
applications their usefulness stems from their time-
frequency localization properties (see e.g., [41).
Whatever the choice for
g
(Gaussian, supported
on
an
interval, etc.), it
is
interesting to know to which extent the
coefficients
cm,(
f
1
of (1.1) define the function
f.
This is
one
of
the main issues of this paper.
The coefficients
cmn(
f)
in (1.1) can also be viewed as
inner products of the signal
f
to be analyzed with a
discrete lattice of coherent states. Let us clarify this
statement. By “coherent states” we understand here the
family of square integrable functions
g(p*q),
generated
from a single L2(R)-function
g,
by phase space transla-
tions
(p,q).
A “discrete lattice” of coherent states is a
discrete subset of the whole family obtained by restricting
the labels
(p,q)
to a regular rectangular lattice in phase
space. “Phase space,” a term we borrow here from physics,
stands for the two-dimensional time-frequency space,
considered as one geometric whole. More precisely,
g(p-9)(x)
is obtained from
g(x)
by a translation of
x
by
q,
and by a similar translation of the Fourier transform
d
by
p,
i.e.,
g(p,q)(
x)
=
e‘Pxg(
x
-
q).
(1.2)
Families of coherent states, as defined by (1.2), are used
in many different areas of theoretical physics. Their name
stems from their use in quantum optics (where the Gauss-
ian choice for
g
is favored,
g(x)
=
r-‘I4
exp(
-
x2/2)>
[5], [6],
but they have since spilled over to many other
fields. See e.g.,
[7]
for a review, including many general-
izations of the original concept.
In
quantum mechanics,
they are particularly useful in semiclassical arguments
because they make it possible to study quantum phenom-
ena in a phase-space setting. If the original function
g
is
centered around
(0,O)
in phase space, i.e., if the mean
value of position,
l&xlg(x)l*,
and of momentum,
/dkkli(k)l2,
are both zero, then the state
g(p.q’
will be
centered around
(p,
q),
i.e.,
0018-9448/90/0900-0961$01.00
01990 IEEE
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
962
IEEF TRANSACTIONS
ON
INFORMATION
THEORY, VOL.
36,
NO.
5,
SEPTEMBER
1990
Here
2
denotes the Fourier transform
of
g,
g(k)=
(2~>-’/~/dxe‘~~g(x). The inner products (g(p.4),
$1
will
therefore “measure” the phase space content of the func-
tion
$
around the phase space point
(p,q).
See e.g.,
[8,
Section V-A.] and [9] for
two
different methods
of
using
coherent states in a study of semiclassical approximations
to quantum mechanics.
A very important property of the coherent states is the
so-called “resolution of the identity.” It has been discov-
ered and rediscovered many times (see the earlier papers
in [7]). A discussion of its relevance for signal analysis can
be found in
[lo].
For the sake of completeness, we give its
(easy) proof in Appendix A. The “resolution of the iden-
tity” says that the map
@
from
L2(R)
into
L2(R2),
de-
fined by
@f(p,q)
=
(g(P~4),f), is an isometry (up to a
constant factor), i.e.,
Here, as in the remainder of this paper,
(f,
g) stands for
the L2-inner product of the functions
f
and g,
B.
Phase Space in Signal Analysis
The appearance of a phase space concept, such as the
coherent states, in signal analysis, is not altogether sur-
prising. As pointed out by
N.
G.
de Bruijn [ll], it is an
entirely natural concept in music. Let us consider a time-
dependent signal, which is a piece of music played (for
the sake of simplicity), by a single instrument. If we
disregard problems with high harmonics, with the “attack”
of the notes, etc. (this is a simple example!), the musical
score corresponding to the piece can be considered as a
satisfactory representation
of
the time-dependent acoustic
signal. A musical score indicates which notes have to be
played at consecutive time steps. Thus, it gives a fre-
quency analysis, locally in time, and is much closer to a
short-time Fourier transform or a coherent states analy-
sis, than to e.g., the Fourier transform, in which all track
of time-dependence is lost, or at least not explicitly recog-
nizable. The notation of a musical score, indicating time
horizontally, and frequency vertically, is really a phase
space notation. Phase space is thus seen to be a natural
concept in signal analysis. This is also illustrated by the
successful use, in signal analysis, of that other phase space
concept, the Wigner distribution, as in [12] or [131.
As long as the continuously labelled coherent states
g(Pxq) are used, we know, from (1.31, that knowing a signal
f
is equivalent to knowing the inner products (g(P34),f).
This need not be automatically true if one restricts the
labels
(
p,
4)
to the discrete sublattice
(mp,,,
nq,),
m, n
E
Z;
(note that this inner product is antilinear in the first
argument and linear in the second argument, following
the physicists’ convention), while
llfll
stands for the
L2-
norm of
f,
-.
~
-
..
Ilfll’=
(f,f)
=
/W(X)I2.
some conditions on
g,p,,q,
will be required. Let us
define the map
T
T:
L2(R)
-+
12(Z2)
Formula (1.3a) implies that
(
1.3b)
This means that a function
f
can be recovered com-
pletely, and easily, from the phase space “projections”
(g(p,q),f). Note that, since (1.3) holds for any g, one can
use this freedom to choose g optimally for the application
at hand. This freedom of choice was exploited in e.g.,
[8,
Section V-A]; it will also be important to us here.
If, instead of letting
(p,
q)
roam over all of phase space,
in a continuous fashion, we rather restrict ourselves to a
discrete sublattice of phase space, then we revert to (1.1).
That is, if we choose
po,
q,
>
0,
and we define
g,n(
.)
=
g(mP,l.n411)
=
eimptbxg(
x
-
nq,)
then clearly (with
x
interpreted as “time,”
po=
v,,
(Tf)m,n
=
(g,,,f)
=cm,(f).
(
1.4)
This map is the discrete analog of the “continuous” map
in Section I-A. For all the cases of interest to us, the
map
T
will be bounded.
To
have complete characteriza-
tion of a function
f
by its coefficients
c,,(f)
we shall
require that
T
be one-to-one. If the characterization of
f
by means
of
the
c,,(f)
is to be of any use for practical
purposes, one needs more than this, however. It is impor-
tant that the reconstruction of
f
from the coefficients
c,,(f)
(which is possible, in principle, if
T
is one-to-one)
be numerically stable: if the sequences
cmn(f),
c,,,(g) are
“close” for two given functions
f
and g, then we want
this to mean that
f
and g are “close” as well. More
concretely, we require that
Allfll’
5
I(gm,,,f)12
5
Bllfl12
(1.5)
m,n
40
=
to)
with A
>
0,
B
<
m,
and A,
B
independent
of
f.
This can
be rewritten, in operator language, as
c,,(f)
=
(gm,,f)
=
(g‘“”l13”“”’,f).
AnsT*TIBn.
(1.6)
This shows that the short-time Fourier transform can
indeed be viewed as the computation of inner products
with a discrete lattice of coherent states.
Here the inequality
TI
I
T2,
where
TI, T2
are symmetric
operators on
L2(R),
stands for
(f,
T,
f
)
I
(f,
T2f
)
for all
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
~
963
f
E
L2(R).
A
set
of
vectors
(4j;
j
E
J)
in a Hilbert space
2
for which the sums
CjE,l(~j,f)12
yield upper and lower
bounds for the norms
llf1I2,
as in
(1.51,
is also called a
frame.
The concept “frame” was introduced by Duffin
and Schaeffer
1141
in the context of nonharmonic Fourier
analysis; see also
[15].
We shall thus require that the
(g,,;
m,n
E
7)
constitute a frame; we shall give the name
frame bounds
to the constants
A,
B.
In a previous paper
[161
particular functions
g
were
constructed, for given
po,
go
>
0
(with
po’qo
<
27r)
such
that the corresponding
g,,
constitute a frame. For this
special construction, the frame bounds
A,
B
are known
explicitly in terms of
g,
and explicit inversion formulas for
T
can be given. In a particular case
of
this construction
one even finds that the inequalities in
(1.51,
(1.6)
becomes
equalities, i.e.,
A
=
B.
Whenever
A
=
B
the frame is
called a
tight frame.
The inversion
cm,(
f)
+
f
then be-
comes trivial; since
T*T
=
An,
one has
f=A-‘T*Tf=A-‘
gm,(gm,,f)
m,n
where the sum converges strongly, i.e.,
Remark:
Note that frames, even tight frames, are not
bases in general, in spite
of
the resemblance between the
reconstruction formula for a tight frame and the standard
expansion with respect to an orthonormal basis. In gen-
eral, a frame contains “too many” vectors. An example in
the finite-dimensional space
C2
is given by
U,
=
e,,
u2
=
-
1/2e,
-k
6/2e2,
u3
=
-
1/2e,
-
6/2e2,
where
e,
=
(1,O)
and
e2
=
(0,l)
constitute the standard basis for
C2.
One easily checks that, for all
U
E
C2,
32
I
(U/,
v)
l2
=
-Ilvll
3
2
/=I
so
that the
(U/;/
=
1,2,3)
constitute a tight frame, with
inversion formula
The
{U,;
I
=
1,2,3)
do not constitute a basis because they
are not linearly independent. In the infinite-dimensional
frames we shall consider in this paper any finite number
of
vectors will be linearly independent in general, but
there will still be “too many” vectors in the sense that any
of them lies in the closed linear span of all the others. If
the vectors constituting a tight frame are normalized, then
the frame constant
A
=
B
indicates the “rate of redun-
dancy” of the frame; if
A=
B=
1
then the frame is
automatically an orthonormal basis.
While the constructions in
[
161
lead to satisfactory and
easy inversion formulas for
T,
they have the drawback
that the function
g
cannot be chosen freely, but has to be
of the very particular type constructed in
[161.
For some
applications however, the window function
g
might be
imposed
a
priori,
and not be of this particular type.
In
that case it is of interest to find ranges for the parameters
po,qo
such that the
g,,,
associated with the triplet
g,po,qo,
constitute a frame.
As
we shall see next,
snug
frames,
which are close to tight frames, i.e., for which the
ratio
B/A
is close to
1,
are particularly interesting,
because they lead to easy inversion formulas with rapid
convergence properties. It is therefore important to have
good estimates for the frame bounds
A
and
B.
One of
the questions we shall address in this paper is therefore
the following: given
g,
1)
find a range
R
such that for
(po,
qo)
E
R
the associ-
2)
for
(po,qO)~
R,
compute estimates for the frame
Once good estimates for the frame bounds
A, B
are
obtained, one can construct a dual function
g
(depending
on
po,qo
as well as on
g;
see Section
II-A
next) which
leads to the easy reconstruction formula
ated
g,,
are a frame, and
bounds
A,
B.
f(x)
=
C
(gmn7f)elmP‘1xg(~--nq,,).
m,n
The function
2
is essentially a multiple of
g,
with correc-
tion terms
of
the order of
B/A
-
1;
the closer
B/A
is to
1,
the faster the series for
2
converges. Obtaining good
frame bounds is important even
if
different reconstruc-
tion procedures are considered, or
if
only characterization
of
f
by means
of
the
cm,(f>=
(g,,,f)
and not full
reconstruction (after e.g., transmission) is the main goal,
since
any
stable reconstruction or characterization proce-
dure can exist only if the
g,,
constitute a frame.
All of these concern expansions with respect to coher-
ent states constructed according to
(1.2).
We shall also
discuss a different type of expansion, the so-called “wave-
let expansion”
[17]
,
[18],
which corresponds to coherent
states of a different type.
D. Wavelets
-
A
Different Kind
of
Coherent States
The coherent states
g(p.4)
all have the same envelope
function
g,
which is translated by the amount
q,
and
“filled in” with oscillations with frequency
p
(see Fig. la).
They typically have all the same width in time and in
frequency. “Wavelets” are similar to the
g(ps4)
in that
they also constitute a family of functions, derived from
one single function, and indexed by
two
labels, one for
position and one for frequency. More explicitly,
where
h
is a square integrable function such that
and where
a,
b
E
R,
a
#
0.
Note that
if
h
has some decay
at infinity, then
(1.7)
is equivalent to the requirement
/dxh(x)=O.
The parameter
b
in the
h(“Xb)
gives the
position
of
the wavelet, while the dilation parameter
a
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
964
,-‘
/
‘,
hl,-6
li
\\
i/
‘\
\
I
\
IEEE
TRANSACTIONS
ON
INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
Re
943
\
1
I1
/I
//
-2,30
I/
I1
II
II
/I
I1
/I
I/
I1
/I
/I
(b)
(a) Typical choice for the window function
g= g,,,
and typical
gm,,.
In this case g(x)=P-’/4exp(-x2/2),
p,
=
T,
q,
=
1;
figure shows
Re
g4&x)
=
T-’/~
cos(4~x)exp[
-(x
-3)2/2]. (b) Typical choice for basic wavelet
h
=
h,,
and a few typical
hm,,.
In this case
h(x)
=
2/fi~-’/~(l- x2)exp(- x2/2),
a,
=
2,
bo
=
1.
Fig.
1.
governs its frequency. For
la1
-=x
1, the wavelet
h(‘*’)
is a
very
highly concentrated “shrunken” version of
h,
with
frequency content mostly in the high frequency range.
Conversely, for
lul
>>
1,
the wavelet
h(‘,’)
is very much
spread out and has mostly low frequencies (see Fig. l(b)).
As a result of this construction, wavelets will be a better
tool than the “canonical” coherent states
g(p,q)
in situa-
tions where better time-resolution at high frequencies
than at low frequencies is desirable.
There exists a resolution of the identity for wavelets as
well as for the canonical coherent sates. One finds, for all
fl,
f2
E
L2(m
See Appendix A. Again, this implies that a function
f
can
be recovered easily from the inner products
(
A(‘,’),
f
),
since
The similarities between the
g(p,q)
associated with the
short-time Fourier transform and the wavelets
h(‘,’)
are
no accident: both families are special cases of “coherent
states associated with a Lie-group,’’ in the first case the
Weyl-Heisenberg group, in the second case the
‘‘U
+
b”-
group or affine group. Wavelets are therefore also called
“affine coherent states.” They were first introduced, un-
der this name, in [19]. They are of great interest for their
own sake, and have led to interesting applications in
quantum mechanics (see, e.g., [20], [211). They are also
related to the use of dilation and translation techniques in
harmonic analysis, which have turned out to be very
powerful tools. It is likely that these techniques, and
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES:
THE WAVELET
TRANSFORM,
TIME-FREQUENCY
LOCALIZATION
AND SIGNAL
ANALYSIS
965
affine coherent states, will find interesting applications in
quantum mechanics problems (see e.g.,
[22]).
We shall not
go into these aspects here. Note that the “resolutions of
the identity” (1.3) and (1.8) can be used as starting points
for the construction of time-frequency localization or
fil-
ter operators
[23],
[24].
E.
Discrete Lattices of Wavelets -The Wavelet Transform
In analogy to the lattice of coherent states associated
with the short-time Fourier transform, which can be
viewed as a discrete subset of the continuously labeled
g(p99),
we shall also consider discrete lattices of wavelets.
We choose to discretize the dilation parameter
a
by
taking powers of a fixed dilation step
a,
>
1,
a
=
a;;l
with
m
E
Z.
For different values of
m
the wavelets will be
more or less concentrated, and we adapt the discretized
translation steps to the width
of
the wavelet by choosing
b
=
nb,,ay,
with
n
E
Z.
This leads to
h
mn
(x)
=
h(‘C,‘‘b~~‘~)(
x)
=
a;m/2h(
aitnx
-
nb,).
(1.9)
As we shall see, it is also important for the discrete case
to have
l&h(x)
=
0.
The “discrete wavelet transform” is the analog
of
the
map defined by
(1.4)
for the Weyl-Heisenberg case.’
Again one can investigate, as in the Weyl-Heisenberg
case, whether the
h,,
and the associated wavelet trans-
form lead to a “discrete approximation” of the resolution
of the identity
(l.B),
i.e., whether a family
of
wavelets
h,,
constitutes a frame. As was shown in [16], it is possible,
given
ao,bo,
to construct explicit functions
h
such that
the associated
h,,
constitute a frame, or even, in particu-
lar cases, a tight frame. These functions
h
are, as in the
Weyl-Heisenberg case,
o,f
a
very
particular type. Typicall?
their Fourier transform
h
has a compact support; since
h
may be chosen in
C”,
the function
h
may have arbitrarily
fast decay, or
Ih(x)
I
I
ck(1+
Ixl)-k
(1
.lo)
with
ck
<03
for all
k
E
N.
In practice, however, the con-
stants
ck
turn out to be fairly large for functions
h
of the
type constructed in [16]. This means that while
h
satisfies
(1.101, its graph is very spread out (see [161); typically the
distance between the maximum
x,
of
h
and the point
x
defined by
sup{lh(y)I;
y
2
x)
=
10-*1h(x,)l
will be an or-
der
of
magnitude larger than
b,,
the translation step
parameter. For practical purposes, it is desirable to use
functions
h
that are more concentrated than this, such as
e.g.,
h(x)
=
(1
-
x2)e-x2/2.
We shall therefore address the
same questions as the Weyl-Heisenberg case, i.e., for
given
h
:
1) find a range
R
for the parameters such that for
(a,,
bo)
E
R
the associated
h,,
constitute a frame;
and
2)
for
(a,,b,)
E
R,
compute estimates on the frame
bounds
A,
B.
‘To
distinguish the
g,,
from
the wavelets
h,,,,
we
shall call the
g,,
“Weyl-Heisenberg” coherent states, after the group with which
they
are
associated (see Section
I-D).
The wavelet transform can be used, like the short-time
Fourier transform, for signal analysis purposes. As in the
short-time Fourier transform the
two
integer indices,
m
and
n,
control respectively, the frequency range and the
time translation steps. There are however some signifi-
cant differences between the two transforms. Some of
these differences may well make the less widely used
wavelet transform a better tool for the analysis of some
types of signals (e.g., acoustic signals, such as music or
speech) than the short-time Fourier transform. Let us
digress a little on a qualitative discussion of these differ-
ences.
F, Qualitative Comparison of the Short-Time Fourier
Transform and the Wauelet Transfom
To illustrate this comparison we give graphs of typical
g,,
and
h,,
in Fig. 1, and of the associated phase space
lattices in Fig.
2.
More specifically, we represent each
g,,
or
h,,
by the point in phase space around which that
function is mostly concentrated. In the Weyl-Heisenberg
case, assuming that
/&
lg(x)I2
=
1
and
/&xIg(x)l2
=
0
=
/dkklg^(k)12,
the lattice points are given by
In the affine case we again associate to every
h,,
the
space localization point
/&xlh,,(x)12
=
nb,a,”
(assuming
that
/&lh(x)I2
=
1
and
/dxxlh(x)12
=
0).
Since the func-
tion
Ifit
and consequently all the
I(~,,)l
is even in many
applications, the choice
/dkkl(h,,)
(k)12
is not appropri-
ate for the frequency localization, since thisA integral is
zero. This is due to the fact that the
(h,,)
have
two
peaks, one for positive and one for negative frequencies.
We therefore represent the frequency content of
h,,
by
two
points, namely
The two lattice points corresponding to the positive and
negative frequency localizations of
h,,
are thus
(nb,a;;,
airn@
5
1
where
w+
=
+k
<,dkklh(k)12.
In Fig.
l(a)
a few typi-
cal Weyl-Heisenberg coherent states were given, in Fig.
l(b) some typical wavelets. Fig.
1
shows one very basic
difference between the two approaches; while the size of
the support of the
g,,
is fixed, the support of the
h,,
is
essentially proportional to
ay.
As
a result, high frequency
h,,,
which correspond to
rn
<<
0,
are very much concen-
trated. This means, of course, that the time-translation
step (if
x
is interpreted as “time”) has
to
be smaller for
high-frequency
h,,,
as shown by the phase space lattice
in Fig. 2(b). It also means, however, that the wavelet
transform will be able to “zoom in” on singularities, using
more and more concentrated
h,,
corresponding to higher
and higher frequencies.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
966
IEEE
TRANSACTIONS ON INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
.
.
.
.
0
.
k
0
. . . .
(b
0
.
. .
4,
. . . .
Ik
......
.ao.k.l(-??
..........
(-CO)
(-4,2)
(0,O)
(0,O
(0,2)
I
....................
(b)
t
corresponds to a value for
m
of approximately
67rf;
‘pi
’.
In practice however, since
T
B
to,
much higher values of
m will be needed to reproduce, by means of the
g,,
sketched in Fig. l(a> (and which all have width
T),
a
function
f
which is nonzero only in the interval
[O,t,].
This is not the case
if
wavelets are used. The high
frequency wavelets have very small support,
so
that the
above problem (having to bring in much higher frequen-
cies than intuitively needed) does not occur. Moreover,
even for the high frequencies corresponding to
f,
which
correspond in the wavelet transform to very negative
values of
m
and a very small time translation step (see
Fig. 2(b)), only a few
of
the many time-steps necessary to
cover
[0,
TI
would be needed, namely only those corre-
sponding
to
[0,
to].
This is what is meant by the “zooming
in” property
of
the wavelets. For this kind of problem,
wavelets thus provide a more efficient way (needing fewer
coefficients) of representing the signal.
I
Fig.
3.
One component of attack of note (see text).
We
take, as model,
Fig.
2.
(a) Phase space lattice corresponding to short-time Fourier
transform (see text).
(b)
Phase space lattice corresponding to wavelet
transform (see text). Constant
k,
is given
by
k,
=
/,”dkk-l16(k)12;
we
have assumed
h
to be even, and we have chosen
a,
=
2.
sin
(6af
/
tn)
,
OSt<t”
0
ts0,
or
f
t
t,,.
Lowest frequency of interest is 2aT-I; typically
to
T.
Let us illustrate this by the following simple example,
taken from a grossly simplified problem in the synthesis of
music. Typically one needs to be able to handle relatively
low frequencies corresponding to the lowest notes and
very high frequencies corresponding to high harmonics.
Suppose one wants to be able to represent tones with
frequency of the order of
27r/T.
Suppose also that one
wants to be able to render faithfully the “attack” of notes.
This “attack” consists
of
very high harmonics at the start
of the note which die out very quickly, typically in a time
to
T.
We have represented one component of such an
“attack” very schematically in Fig.
3.
Intuitively, the func-
tion
f(t)
in Fig.
3
seems to correspond to a signal with
“frequency”
2.sr3/tO
during the time interval
[O,
to],
while
its amplitude on
[[,,,TI
is zero. Let us compare the
performances of discrete Weyl-Heisenberg coherent
states and
of
wavelets for this problem. In the first case,
the support of
g,
and hence that of all the
g,,,
needs to
have a width
of
at least
T.
The high frequency
6r/to
This example is
so
much simplified that it is rather
unrealistic. The “zooming in” faculty of the wavelets,
illustrated by this example, does however play an impor-
tant role in more realistic applications; it makes the
wavelets a useful tool in the areas of signal analysis such
as seismic analysis
[25]
and music synthesis
[26].
This
same property also makes the wavelets a choice tool for
the detection
of
singularities
[27], [28],
which is of great
interest to the analysis
of
vision
[29], [381,
[40],
and for the
study of fractals
[67].
As
a final remark we note that the wavelet transform,
unlike the short-time Fourier transform, treats frequency
in a logarithmic way (as clearly shown by Fig.
2),
which is
similar to our acoustic perception. This corresponds to
constant
Q
as opposed to constant bandwidth filters. This
is another argument for the use of wavelets for the
analysis and/or synthesis of acoustic signals.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
968
IEEE
TRANSACTIONS ON INFORMATION
TIIEORY,
VOI..
36.
NO.
5,
SEPTEMBER
1990
exists a function
JI
such that the JI,,(x)=2-”*JI(2-’x-n),
j
fixed, are an orthonormal basis of the orthogonal
complement
W,
of
5
in
V,-l.
In other words, the inner
products
{(JI,,,f);
n
E
Z)
contain exactly all the informa-
tion that is present in the approximation to
f
at level
j
-
l
(with resolution 2’-‘) but which is lacking in the next
coarser level
j
(resolution
29.
Because of the “ladder
property” of the
V,
it follows that the whole collection
(JI,,;
j,n
E
Z)
is an orthonormal basis of wavelets for
L2(R>.
Readers who would like to learn more about
multiresolution analysis should consult
[361, [371,
or
[381,
where explicit recipes are given for the construction of
wavelet bases, together with examples. Wavelet decompo-
sitions using multiresolution analysis have been imple-
mented in vision analysis
[38], [401.
A short review is also
included in
[39].
Note that there is a connection between
orthonormal wavelet bases and quadrature mirror filters,
used in subband coding
[39], [401.
Incidentally, the discovery of multiresolution analysis is
another instance in which signal analysis applications
provided the first intuition leading to the mathematical
construction. Existing, more rudimentary techniques in
vision analysis inspired
S.
Mallat to view orthonormal
wavelet bases as a more refined tool for multiresolution
approximations, which led to
[361, [37].
S.
Mallat has
implemented these ideas, using the Battle-LemariC bases,
into an algorithm for decomposition and reconstruction of
images
[29], [381.
Finally, in February
1987,
using Mallat’s
algorithm as inspiration, I succeeded in constructing or-
thonormal bases of wavelets with compact support, which
are discussed elsewhere
[39].
These different families of orthonormal wavelet bases
have created quite a stir among mathematicians. Apart
from applications to signal analysis, they should be useful
in physics also. A first application, to quantum field
theory, can be found in
[41].
All these orthonormal bases
are, however, rather spread out numerically, if one wants
h
to be reasonably regular
(h
E
Ck,
with k large enough).
If one
is
willing
to
give up the requirement of a basis
and to settle for a frame (giving up the linear indepen-
dence-see the remark in Section 1-0, then much better
localized
C”
h
can be chosen. This makes frames more
interesting than orthonormal bases for certain wavelet
applications in signal analysis. Another reason is that, as
will be shown later, for a given desired reconstruction
precision, frames allow one to calculate the wavelet coef-
ficients with less precision than would be needed in the
orthonormal case; the number of coefficients calculated
is, of course, higher. This may be useful in some numeri-
cal applications. The present paper addresses “frame”
questions. We shall formulate criteria under which the
h,,
constitute a frame, and then derive some properties
of
these frames. Since similar techniques can be used for
Weyl-Heisenberg coherent states, we address the same
questions for that case as well. The basic results of this
paper were reported, in an abridged version, at two
mathematics conferences, in March
1986
[42] and July
1986 [43],
respectively.
H.
Organization
of
the
Paper
In Section
I1
we study “frame questions.” We start with
some generalities concerning frames in Hilbert spaces.
We review the construction of
[16],
leading to tight frames.
For more general choices of the initial function
g
or
h,
we answer the questions
1)
and
2)
asked previously (suffi-
cient condition for frame, estimates for the frame con-
stants
A
and
B),
both for the Weyl-Heisenberg and for
the wavelet case. We discuss whether certain ranges for
po,
4,)
or
a,,,
6,)
are
a
priori excluded, and we give inequal-
ities linking
A,
B,
g,
or
h
and po,qO or
aO,bO.
We give
many examples, and numerical tables of frame constants
for these examples. For particular choices of
g
or
h,
our
results can be translated into estimates on entire func-
tions
[44].
A special case of this kind of estimate was
already given in
[451.
Since numerically one is also inter-
ested in convergence in other topologies than only
L2,
we
address the question of convergence in other spaces as
well. To improve the readability
of
the paper, we have
relegated many of the technical proofs to appendices.
In Section 111 we show how to use these frames for
phase space localization. Concretely this means the fol-
lowing. Suppose that a signal
f
is mostly concentrate$ in
[-
T,T]
in time, and that its Fourier transform
f
is
concentrated mostly between the frequencies
fl,
and
Oz.
This means that in phase space,
f
is mostly concentrated
on
[-T,T]X([-LR2,
-flI]U[LRI,f12]).
One would then
expect that only those phase space lattice points, in Fig.
2,
lying within this box (plus those lying
very
close to it)
would suffice to approximately reconstruct
f.
It turns out
that this intuition is essentially right. Note that such a
“box” contains only a finite number of points. We also
show how the “over-sampling’’ inherent to working with
frames permits, for fixed desired precision on the recon-
struction of
f,
to compute the coefficients
c,,(f)
with
less precision than would be needed in the orthonormal
case.
I.
Some Remarks
A
first remark we want to make is that while we shall
stick, throughout the paper, to one dimension (i.e., a
two-dimensional phase space), it is possible to generalize
the results to more than one dimension. For the
Weyl-Heisenberg case this is trivially true. For the wavelet
case two possibilities exist. In the first case dilations and
translations are used, independently in the
n
dimensions,
and then again the extension is trivial. In the second case
one uses n-dimensional translations, but only one dilation
parameter, which acts simultaneously on all dimensions.
In this case several (a finite number)
hi
have to be
introduced. This construction is then similar to the gener-
alization in
[32]
of
Y.
Meyer’s basis to
II
dimensions: in
that case
2“
-
1
different functions
hi
are used.
A
second remark is that we, have restricted ourselves
here to regularly spaced lattices, in the Weyl-Heisenberg
(WH) case as well as the wavelet case. While it is possible
to relax this regularity somewhat (we can also handle the
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
969
WH case
if
one of the two variables,
p
or
q,
is not
regularly spaced, as long as the other is; likewise, in the
wavelet case, we can handle dilations that are more
irregular than the geometric sequence
ay),
the methods
presented here are essentially unable to cope with distri-
butions of phase space points that would have the same
density (and this probably suffices to define frames, as in
nonharmonic Fourier analysis
[
1511, but which would not
be given by lattices. Using different methods, one can
indeed show that less regular phase space point distribu-
tions with a sufficiently high density do indeed lead to
frames. For very special choices of
g
or
h
for which the
“frame questions” can be formulated as properties of
entire function spaces, that was proved in [451, [47]. Using
the full power of the underlying group structure,
Feichtinger and Grochenig [48] proved the same result for
much more general functions
g
or
h
(essentially, they
only require that
g
or
h
is reasonably “nice”), without
recourse to entire function spaces. The results in [46]-[48]
are, however, more qualitative than quantitative in that
they establish that certain discrete families of coherent
states constitute frames without caring too much about
the values
of
the frame constants. Moreover, the phase
space densities of the discrete families considered in
[46]-[48] seems
to
be considerably higher than in our
examples.
11. FRAMES
AND
FRAME BOUNDS
A.
Generalities Concerning Frames
We start by reviewing some general properties of frames
Suppose that the
(4,;
I
EJ)
constitute a frame in the
Hilbert space
A?,
i.e., there exist
A
>
0,
B
<m
such that,
for all
f
E
2,
[141,
[151.
AlIf11’1
I(4,,f)I2
I
Bllfll’. (2.1.1)
I6
J
Define
T:
A?-+I’(J)
by
(Tf),=
(4/,f).
Here
I’(J)
stands for the space of square summable complex se-
quences indexed by
J.
The operator
T
is clearly bounded,
llTf
11
I
B1’’1l
f
11.
We shall call
T
the “frame operator”
associated with the frame
(41)lEJ.
Its adjoint operator
T*
maps
I2(J)
onto
2;
it is defined by
T*c
=
CIEJc,4/,
where
c
=(c/)/~~
E
12(J).
The frame inequalities (2.1.1)
can be rewritten as
AllsT*TIBll.
Since the symmetric operator
T*T
is bounded below by a
strictly positive constant, it is invertible, with a bounded
inverse. This inverse satisfies
B-’l
I
(T*T)-’s
A-lll.
(2.1.2)
Define
6,
=
(T*T)-’+,.
Then the family
($,),,,
consti-
tutes another frame. More precisely, we have
Proposition
2.
I:
1) The family
($l)ltJ,
with
$,
=
(T*T)-’4,,
constitutes
a frame with bounds
B-’
and A-’.
2) The associated frame operator
f
is given by
f=
f*f
=
(T*T)-’
f*T
=
1
=
T*f
T(T
*T)-’
and satisfies
(2.1.3)
where
fT*
=
Tf*
is the orthogonal projection oper-
ator, in
/’(I),
onto the range of
T.
Proofi
For any
f
E
2,
we have
<&f>
=(
(T*T)-%,f)
=(
4/,(T*T)-’f)
*
Hence
ci($,,f)i’=
IIT(T*T)-’~II’
=(
f,(T*T)-’f).
I
=
(
(T*T)
-‘~,T*T(T*T)
-If)
It then follows from (2.1.2) that the
<$,),,,
consti-
tute a frame, with frame _bounds
B-’
and A-’.
By the definition of the
4,
we have
(ffh
=
<$,,f>
=
((T*T)-’4/?f)
=
($/,(T*T)-’f)
=
(T(T*T)-’f),,
hence
T-
=
T(T*T)-’.
It follows that
f*f
=
(T*T)-’T*T(T*T)-’
=
(T*T)-’
F*T
=
(T*T)-’T*T
=
n,
and
T*f
=
T*T(T*T)-’
=
1.
Finally
fT*
=
T(T*T)-IT*
=
Tf*;
it remains to
prove that this is the orthogonal projection operator
P
onto the range
of
T.
Since
T*c=O
for any
c
orthogonal to the range of
T,
it suffices to prove
that
T(T*T)-’T*c
=
c
for
c
in the range of
T.
If
c
is in the range of
T,
c
=
Tf,
then
T(T*T)-’T*c
=
T(T*T)-’T*T~=
~f=
C.
This proves
fT*
=
P
=
Tf*.
U
The operation
{4/;
I
E
1)
-+
{$/;
I
E
J)
defines, in a
sense, a duality pperation. The same procedure, applied
to the frame
($/;
I
E
J),
gives the original frame
{4[;
1
E
J)
back again. We shall therefore call
(6,;
E
J)
the
dual
frame
of
{4/;
1
E
J).
The duality
4,-
4,
is also
expressed
by
(2.1.3); for any
f,g
E
2
we have
(f,g)
=
c
(f?$/)(4/A)
=
c
(f?4/x$/,g).
IEJ
I€J
In what follows we shall
so
often encounter
T*T
(rather
than
T
alone) that
it
makes sense to introduce a new
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
970
IEFF
TRANSACTIONS ON INFORMATION THEORY,
VOL.
36.
NO.
5,
SEI’TEMHFR
1990
notation for this operator. We define
- --
U=
T*T,
U=
T*T
=U-’.
In particular
U=
c
4/(4/,*)
AnlulBn
&=U-’(b/.
IcJ
Proposition 2.1 gives us an inversion formula for
T.
If the
elements
f
E
2
are characterized by means of the inner
products
((
f,c$/);
1
E
J),
then
f
can be reconstructed
from these by means of
f
=
Ci1<4/,f)
I
valid” choices
is
used, where
&/
is replaced by 2/3(4,
+
a).
Of all the possible “quasi-inverses” for
T, T*
is therefore
the only one that automatically projects sequences in
(RanT)
A
similar phenomenon occurs with the infinite-dimen-
sional frames we shall consider. While no finite number
of them will be linearly dependent, there generally do
exist convergent linear combinations, involving infinitely
many
+/,
which sum to zero. This again causes “recon-
struction formulas” to be nonunique, but again the
4l
=
will offer the optimal solution, in the sense that
they are the
only
choice leading to
to zero while effecting the reconstruction.
ZC,~,
=
0,
for all
c
=
(c/)/,~
I
RanR.
(2.1.4)
I
In (2.1.4) the vectors
&/
are defined by
&/
=U-’4,.
Note
that, in general, if the frame is redundant (i.e., contains
“more” vectors than a basis would), there exist other
v_ectors in
2
that could equally well play the role of the
4/
and lead to a reconstruction formula. This is due to the
fact that the
4/
are not linearly independent in the
general case. This phenomenon can be illustrated with
the two-dimensional example of Section
I-C.
Take
2
=
C2,
and define
4,
=e,,
+3
=
-
2“’
-
?e2
2
where
e,
=
(l,O),
e2
=
(0,l) constitute the standard or-
thonormal basis in
C2.
One can check very easily that for
all
U
E
X,
16
16
42
=
-
2“’
+
-e2,
23
2
c
1(4/4)l
=
-IlUll
3
2
I=1
so
that
U=
3/21, hence
becomes
=U-’+,
=
2/34,, and (2.1.4)
23
U
=
-
c
4/(4/,U>.
3
1=1
Since
C:=
,4/
=
0 in this example, it is clear, however, that
for any choice of
a
E
2,
an equally valid reconstruction
formula is given by
23
U
=
-
c
(4/
+
a)(4,,u).
3
I=1
The choice
a
=
0, corresponding to (2.1.4), is the “minimal
solution” in the following sense. The image, in C3, of
C2
under the frame operator
T
is the two-dimensional sub-
space with equation
x,
+
x2
+
x3
=
0; we denote this sub-
space by
RanT.
Vectors in
C3
orthogonal to
RanT
are all
of the type
c
=
A(1,1,1). When the components of such a
vector are substituted for the
(4/,~)
in (2.1.4), then the
“reconstruction” leads to
0,
since
This is easy to check by the following argument. Write
4/
=
U-’C$/
+
U,,
and suppose that (2.1.4) holds. It follows
that
Cu,(4,,f)
=
0, for all
f
E
2,
or
Cu,c,
=
0, for all
c
E
RanT.
The optimality condition implies
Cu,c,
=
0
for
all
c
1
RanT.
It follows that
Cu,c,
=
0 for all
c
E
12(J),
hence
U/
=
0 for all
1.
To apply (2.1.4) it is, of course, necessary to construct
the first. Writing
U
as 2(A
+B)-L[n
-(2(A
+B)-’U)l,
one has the following series for the
$/,
Since
A-B
2u
B-A
A+B A+B-B+A
nsn--<-
n
or
<1
(2.1
-6)
the series in (2.1.5) always converges. The closer B/A is
to
1,
the faster the convergence, of course.
Remark:
For the reconstruction formula (2.1.4) for
f
from its coefficients
($,,f),
we have used (2.1.3), namely
that
f*T
=
n.
One can also interpret (2.1.3) differently.
From
T*f
=
1
it follows that, for all
f
E
2,
f=
c
<&f>4/.
I
This tells us that any function
f
can be expanded in the
4/,
and gives
us
a recipe for calculating appropriate
coefficients. This is the point of view taken in so-called
“atomic decompositions.”
It
is thus clear that frames and
atomic decompositions are dual notions [481.
All the previous formulas become much simpler
if
the
frame
is
tight,
i.e.,
if
B
=
A.
In that case
u=An,
f=A-ln
&
=
A-@/
f=
A-’
c
4/(4/>f>.
It
J
If the frame constant for a tight frame is equal to one,
This is no longer the case
if
one of the other “equally
A
=
1, then the reconstruction formula looks exactly like
I=
1
I=1
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREOUENCY LOCALIZATION AND 5IGNAL ANA1
YSlS
~
97
1
the decomposition of a function with respect to an or-
thonormal basis,
f=
c
h(4l.f).
IEJ
In fact, if the vectors in a tight frame with frame constant
1
are all normalized, then the frame constitutes an or-
thonormal basis, as can easily be seen by the following
argument:
ll4k1I2
=
I
(4/?4k)
l2
IEJ
=l14k114+
c
I(4/?4k)12
IE
J
which implies
(41,4k)
=
0
for 1
#
k
if
ll+kll
=
1.
As
we
explained in the introduction, there are circumstances in
which one_ prefers to work with nontight frames. In that
case the
4)
have to be constructed explicitly from the
c$/.
Formula (2.1.5) then gives an algorithm for the computa-
tion of the
6,;
as (2.1.6) shows, it pays to have a ratio
B/A
as close to 1 as possible. Frames that are almost
tight (i.e.,
B/A
close
to
1) will be called snugframes. The
"snugness" can be measured by
S
=[B/A
-11-'. In the
examples below we shall encounter values of
S
2
100,
corresponding
to
B/A
of the order of 1.01 or even
smaller, for quite realistic frames (i.e., reasonably large
values of
po,
qO
or
a,,
bo-see Introduction).
Note also that, while in principle all the different
il,
1
E
J,
have to be calculated separately, in practice simpli-
fications may occur. Let us show what happens for the
discrete Weyl-Heisenberg coherent state frames and for
the wavelet frames defined in the introduction. We take
therefore
3
=
L2(R>,
J
=
Z2.
In the Weyl-Heisenberg case, we can rewrite
U
as
U=
C
W(mP,,nq")g( Wh,,nq,)g,
.>
m,n
E
h
where the operator
W(p,q)
is defined by [W(p,q)g](x)
=
eiPXg(x
-
9).
One easily checks that W(p,
q)W(p',
4')
=
e-'P'qW(p
+
p',q
+
4').
Using this multiplication for-
mula for the operators
W,
one easily finds that
W(
mp,,
nq,)T
=
TW(
mp,,
w,).
W(
mp,
,
nq,
)
U-
=
U-
'
W(
mp,,
nq,
.
Hence
This implies
(grnn)"
=T-'grnn
=
U-
'
W(
mp,,
9
w,,)
g
=
W(
mP0
7
n9,)T-
or
(gmn)"(x)
=
eirnpox(go0)'(x
-
nq,)
=
grnn(x>, where
=
(goo)-
=
T'g.
We have thus only one function to com-
pute, i.e.,
goo
=U-'g,
instead
of
a double infinity of
different (gmn)"(m,
n
E
Z).
If moreover
B/A
is close to
1, then the rapidly converging series (2.1.5) can be used
for this computation.
In the affine case, we find
U=
U(
a;;,ar
nb,,)h(
U(
ar,nr
nb,)h,
.)
m,nEH
where
[U(a,b)f](x)=
l~l-'/~f(x
-
b/a).
Again we can
use the composition law
U(
a',
b')U(
a",
b")
=
U(
a'"',
b'
+
a'b")
U(a~,O)T=UU(a;;,O).
to show that
Note that we have no translation in these U-operators; it
turns out that
U
does not commute with
U(ar,
nb,
a:)
if
n
#
0.
Since
U(ar,
ay
nbo)
=
U(a:,O)U(l,
nb,),
we find
(hrn,,)-
=
U(ar,O)U-'U(l,nb,)h
or
(
hmn)-( x)
=
hen)-(
a,"x).
The simplification is less drastic than in the WH case,
since only one of the
two
indices is eliminated, and one
still has to compute the infinite number of
(h,,)"
=
U-Ihtrn. In practice, however, only a finite number are
needed, and for the computation of these it is again a big
help
if
B/A
is close to 1.
Note that
if
one stops at the first term
(k
=
0)
in (2.1.51,
one obtains the approximate inversion formula
.-,
If
B/A
is close enough to one, this is a fairly good
approximation.
In
the first calculations with wavelets, the
formula used for analysis and reconstruction was
very
similar
to
(2.1.7) [25], without theoretical basis. It turns
out that in those frames
B/A
was indeed
vcry
close
to
1,
so
that
fapprox
is a good approximation
to
f.
B.
Tight Frames
1)
Explicitly Constructed Tight Frames: In this subsec-
tion we review shortly, for the sake of completeness, the
explicit construction
of
tight frames given in [16]. We have
drawn inspiration from [31] to make the construction
more elegant. For examples, graphs and a more detailed
discussion we refer to [16].
In both cases an auxiliary function
v
of the following
type is used
v:R-tR
If
v
is chosen to be a
Ck
(or
C")
function, then the
resulting frames will consist of
ck
(em)
functions.
a)
The Weyl- Heisenberg case: Choose
p,,
q,
>
0,
with
pO.qO
<
2~. (In Section 11-C we shall have more
to
say about this restriction.) We shall assume here that
po.qo
2
n-.
(See [16, Appendix] for indications how the
construction can be adapted
if
po-qo
<
T).
Define
A
=
27r/p0
-
qo;
one has
0
<
h
I
r/pO.
The function
g
is
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
912
IEEE
TRANSACTIONS
ON INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
fi(Y)=(10gao)-'/2(
then constructed as follows:
sin[
:U(
)]7
1
I
y
5
a,l
cos['u(
Y-a,l
)]
a,lIy5a;l
2 la,(a,-1)
'
71.
I
sin
[
iv(
A-'(
+
x))],
-
r/pi,
I
x
I
-
-
+
A
PO
-+A
71.
I
x
<--A
71.
Po
PO
71.
7T
I
COS[
:U(
A-'(
x
-
+
A))],
-
-
A
5
x
5
r/p0
PO
The overall factor
qo1I2
normalizes
g;
one easily checks
that
ldxlg(x)I2
=
1.
The following two properties of
g
are
crucial.
These two properties together ensure that the
gmn,
g,,Jx)
=
eimpOxg(x
-
nq,),
constitute a tight frame. By
Plancherel's theorem we have indeed for all
f
E
L2(R),
One finds thus
gm,(x)
=
G(x)-'gmn(x),
and the inversion
formula becomes
Remark:
If the function
U
is chosen to be
C",
then
g
is
a compactly supported C"-function. While the uncertainty
principle can of course not be violated, this nevertheless
allows fairly good localization of
g
in
both time and
frequency. The coefficients
(g,,,
f
)
do therefore corre-
spond to a reasonably accurate time-frequency localized
picture of the signal
f.
Moreover, there exists a constant
A
=
271./p,.q,
such that
where we have used the notation
g(y)*
to denote the
complex conjugate of
g(y).
Note that the same calcula-
tion can be made whenever lsupport
gl
I
271./p0,
even
if
(2.2.1)
is not satisfied.
In
that case the operator
U
of
Section
11-A
reduces to multiplication by the periodic
function
G(x)
=
271.p~'C,,,Ig(x
-
nq,,)12
(see also
[50]).
2
The role of this constant
A
is crucial. If one restricts
oneself to
A
=
1,
then this forces the
g,,
to be an
orthonormal basis, which leads to functions
g
that are
badly localized in either time or frequency. This is a
consequence of the Balian-Low theorem
[51], [52]
(Theo-
rem
2.3
next), rediscovered in
[53].
As
soon,
however, as
one allows
A
#
1,
the picture changes drastically, and
much better time-frequency localization is attainable.
b) The wavelet case:
In
this case there are
no
a
priori
restrictions
on
the choice of the parameters
a,,
bo,
other
than
a,
#
0
or
1
and
6,
#
0.
We may choose, without loss
of generality,
a,
>
1,
and
b,
>
0.
Define
1
=
271./[b,(a:
-
l)].
The tight frame of wavelets will be based
on
the
function
h
with Fourier transform
fi
constructed as fol-
lows
[16]:
y5l
11-1
\1
(2.2.2)
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
973
The function
h
itself is given by the inverse Fourier
transform,
The normalization of
h
has been chosen
so
that
/dYlYl-’ll;(Y)[2
=
1.
2)
C
l+6Y)12
=(log%-lX[o,m,(Y)>
The following
two
properties of
h
are again crucial:
1)
Isupport
l;~
=
(ai
-
I)/
=
2r/b,,
(2.2.3)
k=Z
where
x[,,,,)
is the indicator function of the right half line,
X[,,~)(Y)
=
1
if
y
2
0,
x[,,,,,(y)
=
0,
otherwise. These prop-
erties together enable us to construct a tight frame based
on
h.
By Parseval’s theorem, we have, for all
f
E
L2(R),
C
I(hmn,f)12
m,n=Z
m,n
E
L
(2.2.4)
If we define
h+
=
h, h-
=
h*
(i.e.,
(h-
T
(k)
=
fi(
-
k)),
then this calculation shows that the
(h&;
m,n
E
Z)
con-
stitute a tight frame. Specifically,
llfl12.
(2.2.5)
C
C
I(hLn7f)l
==
2
27.r
€=+or-
m,nEL
Similarly the
(h‘,“:;
m,
n
E
h,
A
=
1
or
21, with
h(’)
=
Re
h,
h‘”
=
Im
h,
constitute a tight frame. Strictly speaking, the
frames
(h;,;
E
=
+
or
-,
m,n
E
Z)
or
(h‘,“:;
A
=
1
or 2,
m,n
E
Z)
are not quite of the type described in the
introduction, since they are not obtained by dilating and
translating one single function.
As
shown by the computa-
tion leading to (2.2.4), the operator
U
=
T*T
handles the
positive and negative freque2cy domains independently.
Since the Fourier transform
h
of
h,
defined by (2.2.2), is
entirely supported on the positive half line, the use of a
second function, which will handle the negative frequen-
cies, is therefore unavoidable. In other examples (see e.g,
Section 11-C-2) the function
h
will be chosen such that
h
is supported on both the negative and the positive half
lines, and one function suffices.
Let us return to the construction (2.2.2). For a special
set
of
signals
f
Lo
be analyzed, one may restrict oneself,
even if support
h
c[O,m),
to only one basic function
h,
and the associated wavelets
h,,,,,.
This happens if one
knows
a
priori,
as is often the case, that the signal
f
is
real. Since then
f(
-
y)
=
f(y)*,
one finds
As
for the Weyl-Heisenberg case, a calculation similar to
(2.2.4) can be carried out whenever the support width
of
h
is smaller than 27r/b,, even
if
(2.2.3)
is
not satisfied.
The operator
U
becomes then
(Tf)^(Y)
=
fi(Y)f(Y)
with
or, equivalently,
Hence
In the construction of the orthonormal basis,
in
1
1311, the
procedure starts in the same way. The function
v
is
chosen to be
C”,
and has one additional property,
(2.2.6)
The “doubling” (using superscripts
+
to be able to cover,
in Fourier space, the whole real line instead of only the
half line) is avoided in [31] by incorporating also the
mirror image
of
h
into the basis function
I,/J.
Explicitly,
v(
x)
+
v(
1
-
x)
=
1,
for all
x
E
R.
Due to the extra property (2.2.6) of
v,
one easily checks
that
11$112
=
jk
II,/J(x)12
=
1.
Note that the size of the
support of
6
is no longer equal to 2r/b,,
so
that the
straightforward calculation made previously no longer
works. In fact, the set of functions
I,/Jmn(x)
=
U,~/~I,/J(U;”~
-
nb,),
m,
n
E
Z,
turns out to be an or-
thonormal basis of
L2(R)
as the result of some miraculous
cancellations, for which the property (2.2.6) of the func-
tion
v
turns out to be quite crucial [31]. These cancella-
tions occur only when
a,
takes on a very special value,
namely when
k+l
a,
=
-
with
k
E
N.
k’
The case
k
=
1, or
a,
=
2, corresponds to
Y.
Meyer’s
construction in [31]. With
b,
=
1
(as in [311),
Y.
Meyer’s
basic wavelet is thus given by
1
f(
y)
=
-e’y/2[w(
y)
+
w(
-
y)]
(2.2.7)
fi
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
974
IEEE
TRANSACTIONS ON
INFORMATION THEORY, VOL.
36,
NO.
5,
SEPTEMBER
1990
with
4Y)
=
4rr
3
8rr
3
where
v
is a
C"
function from
R
to [0,1] such that
v(y)
=
0
for
y
I
0,
v(y)
=
1
for
y
2
1 and
v(y)+
v(1-
y)
=
1
for all
y.
As
pointed out in the introduction, the
concept of multiscale analysis allows one to understand
more deeply why this construction works,
so
that the
"miraculous cancellations" just mentioned become less
2)
Relations Between the Frame Parameters and the
Frame Bounds:
In the explicitly constructed tight frames,
the frame constant
A
is given by
A
=
27r/p0q0, for the
Weyl-Heisenberg case, and by
A
=
rr/
b,
log
a,,
for the
affine or wavelet case. This is no coincidence. We show in
this subsection that these values for
A
are imposed by the
normalizations chosen for
g,h,
and are independent of
the details
of
the construction, i.e., they are generally true
for
all
tight frames. More generally, we prove inequalities
for the frame bounds
A,
B
for
all
Weyl-Heisenberg
frames or wavelet frames, tight or not.
a)
The
Weyl-
Heisenberg case:
Let us assume that the
(+",,;
m,n
E
Z)
are an arbitrary frame of discrete
Weyl-Heisenberg coherent states, with frame constants
A,
B,
and lattice spacings
p,,
q,,
i.e.,
+mn(
x)
=
eimpox+(
x
-
nq,),
so.
Allfll'
l
c
I
(+,,,f)
l2
I
Bllfll'.
m,n
We shall see next that a frame is possible only if
po'qo
I
257. Let
us
therefore restrict ourselves to this case. Then
there exists, for the same values
po,qo,
a tight frame
This is true for any Weyl-Heisenberg-frame with lattice
spacings
pO,
qo.
In particular,
if
the
c$",,
constitute a tight
frame (i.e.,
A
=
B),
then necessarily
2rr
Po40
A
=
-114112.
a)
The wavelet case:
In this case also we shall derive
inequalities similar to (2.2.9). Since there is no equivalent
to (2.2.8) for wavelet frames, the derivation will be slightly
more complicated. Let us assume, again, that
(c$mn;
m,n
E
H)
is an arbitrary frame
of
wavelets, with lattice spac-
ings determined by
a,,
bo,
and with frame constants
A,
B,
i.e.,
+,,,(
X)
=
U,"/'+(
aomx
-
nb,)
Allfll'
I
c
l(+mn,f)
1'
I
Bllf1I2.
(2.2.10)
m,n
Take now any positive operator
C
which is trace-class,
i.e., which is
of
the form
c
=
cc,uI(u,,
*)
1
where the
uI
are orthonormal,
c,
>
0
and tr
C
=
C,c,
<W.
Then (2.2.10) implies
l
1
m,n
1
or
We shall apply this to the following operator,
da db
U'
c
=
//
-h(",b)(
*
)t
(
a,
b)
(2.2.12)
constructed with the help of the affine coherent states
introduced in SeFtion I-D. The function
h
E
L2(R)
should
satisfy
Jdy
lyl-'lh(y)I2
<w
(see Section I-D). Here
t(a,
b)
is a positive function in
L'(R*
x
R;
a-'dadb).
The opera-
tor (2.2.12) is positive and trace-class, with
da db
tr
C
=
/Tt(
a,
b)
{gmn;
m,n
E
HI
with
llgll=
1.
(For
po-qo
<
2rr, we take
g
as constructed in Section 11-B-la); for
pn'qn
=
2rr, take
where we have assumed
llhll=
1.
On the other hand,
--
g(x)
=
4;
'1'
if
1x1
I
4,
/2,
g(x)
=
0,
otherwise). One eas-
ily checks that
It follows that
=
1
(+,U(
a{",agrn
nb,)-'U( a,b)h)l't(a,b)
(
+mn,
C+,,>
(g,
4
-m -n
>
.
(2.2.8)
da db
=
(+,U(a;",a,"
nb,)-'CU(a~",a~" nbo)4)
(
gmn,
4)
=
e-imflP,19,
(2.2.13)
where we have used the composition law
of
the U-oper-
Similarly
Bllg112
2rr~P0q,~~+~~2. Since
llgll
=
1,
we
find
AI-II411
2rr
2
IB.
(2.2.9)
ators. We now restrict ourselvks to functions
t
of the form
t(a, b)
=
X[I,",,[(
lab . tl(
b/
1.1)
where
XL1,",,)
is the indicator function
of
the half open
Po40
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL. ANALYSIS
915
interval
[l,
an),
i.e.,
,y~l,ol,p
=
1
if
1
5
U
<
a,,,
0
otherwise.
Since
~rn,y~I,oo)(al;llal)
=
1,
(2.2.13) then leads to
m,n
C
(4rnn,C4rnn)
This sum over
n
can be estimated by the following lemma.
Lemma
2.2:
Let
f
be a positive, continuous, bounded
function on
R,
with
f(x)
+
0
as
1x1
--)W.
Assume that
f
has a finite number of local maxima, at
xi,
j
=
1;
.
.,
N.
Define
x,-S+I
Ai=
sup
1
hf(x).
SE[O,I]
x,-a
Then
For the sake of completeness we provide a proof for the
case
N
=
1;
the case for general
N
can be proved analo-
gously, though the inequalities can be sharpened
if
some
of
the
xi
are within a distance
1
of each other.
Proof:
Let
n,,
be the largest integer not exceeding
xl,
the point where
f
reaches its maximum. Since
f
is in-
creasing on
(-m,xl]
and decreasing on
[xl,m),
and since
no
I
x,
<no
+1:
maximum, at
x
=
xl,
then
m
hf(x)-f(x,)
5
c
f(n)
5j-m-mw(x)+f(xl).
/_b
n
=
--m
Let us apply this to (2.2.14). Choose
F
to be any positive,
continuous
L1
function on
R,
tending to zero at infinity,
with one local maximum, at
x=O.
Choose
A>0,
and
define
tl(
x)
=
F(
AX).
Applying Lemma 2.2 to (2.2.14) then leads to
or
2
=
-
log
ao./duF(x).
(2.2.16)
A
Inserting (2.2.15) and (2.2.16) into (2.2.111, and taking the
limit for
A
--)
0
leads
to
T
jdy
Iyl-'If(
y)
1'
I
B.
(2.2.17)
AI-
bo
1%
a0
These inequalities hold for
any
frame
of
wavelets
$rnn
Incidentally, (2.2.17) shows that the basic function
4
for a
frame of wavelets must 2atisfy the same "admissibility
condition," i.e.,
/dylyl-'14(y)12
<CO,
as the functions from
which continuously labeled affine coherent states are con-
structed (see Section I-D). In particular, if the
4rnn
consti-
tute a tight frame
of
wavelets, then
In the explicitly constructed tight frames in Section II-B-
lb,
two functions (either
h
*,
with
h+
=
h,
h-
=
h*,
or
h(*),
A
=
1,2, with
h(I)
=
Re
h,
h(')
=
Im
h)
were needed to
construct tight frames of wavelets (i.e., the
h;,,
or the
h',":,
A
=
1,2). For such frames the arguments lead to the
frame constant
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
976 IEEE TRANSACTIONS ON INFORMATION THEORY,
VOL..
36,
NO.
5,
SEPTEMBER 1990
This agrees with the value
A
=
257/
bo
log
a,,
obtained in
Section 11-B-Ib (see (2.2.5)), sinFe we chose the normal-
ization of
h
such that
{dy lyl-'lh(y)l2
=
1.
C. General (Not Necessarily Tight) Frames in
L2(
R)
-
Ranges for the Lattice Spacings
-
Frame Bounds
As we already explained in the introduction, it may be
necessary in some applications to resort to nontight
frames. This can be the case
if
the basic function
g
or
h
is
imposed
a
priori
(because
of
its adaptation to the problem
at hand), or in the case of wavelets, when the explicit
examples of functions
h
leading to tight frames are too
spread out.
In this section we treat the following questions:
1) Is there a range of parameters that is excluded
a priori
(i.e., independently of the choice of
g
or
h)?
2) Given
g
(or
h),
determine a range
R
for the param-
eters
po,qo
(resp.
ao,bo)
such that
if
(po,qo)
E
R
(resp.
(ao,
bo)
E
R),
then the associated
g,,
(resp.
hmn)
constitute a frame.
3) For
g,po,qo
(or
h,ao, bo)
chosen as in 21, compute
estimates for the frame bounds
A
and
B.
In order to interrupt the flow of the exposition as little as
possible, we relegate all the technical proofs for this
section to Appendix
C.
1)
The
Weyl-
Heisenberg Case:
a)
Critical value for the product po. qo:
In the
Weyl-Heisenberg case there exists a critical value, 257,
for the product
po.qo.
This is already illustrated by the
construction in Section 11-A-la), which only works
if
po.qo
<
257. The following theorem states that at the
critical value
po*qo
=
257, only functions
g
that are either
not
very
smooth or do not decay very fast can give rise to
a frame.
(Balian
-
Low
-
Coifman
-
Semmes):
Choose
gE
L2(R),
po
>
0.
If the
g,,
associated with
g,po,qo
=
2n-/p0,
constitute a frame, then either
xg
E
L2
or
g'
E
L'.
Remark:
This theorem was first published by
R.
Balian
[51] for the case where the
g,,
are an orthonormal basis.
In the 1985 Festschrift for the 60th birthday of the physi-
cist
G.
Chew,
F.
Low also discusses this problem [521. He
gives (independently) essentially the same proof as in [511.
The proof presented in [51], [52] contains a technical gap
that was filled by
R.
Coifman and
S.
Semmes. The proof
extends easily from the basis case to the frame case. We
give here the proof as completed by
R.
Coifman and
S.
Semmes.
The proof of Theorem 2.3 uses the Zak transform
U,.
This transform maps L2(R) unitarily onto L2([07 112); it
was first systematically studied by J. Zak [541, in connec-
tion wjth solid state physics. Some of its properties were
known long before Zak's work, however. In [551 the same
transform is called the Weil-Brezin map, and it is claimed
that the same transform was already known to Gauss. It
Theorem
2.3
was also used by Gel'fand (see, e.g., Ch. XI11 in
[561).
J.
Zak seems, however, to have been the first to recognize
it as the versatile tool it is and to have studied it systemat-
ically. It has many very interesting properties; its applica-
tions range from solid state physics to the derivation, in
[57], of new relationships between Jacobi's theta func-
tions. Before embarking on the proof of Theorem 2.3, we
briefly review the definition and some of the properties of
U,.
The Zak transform
U,
is defined by
(Uzf)(t,s)
=A'/2
e2T'f'f(A(s-1))
(2.3.1)
where the parameter
A
>
0
can be adjusted to the prob-
lem at hand. For the proof of Theorem 2.3 we shall take
Strictly speaking, the definition (2.3.1) does only make
sense for the subspace of the L2-functions for which the
series converges. It is, however, easy to extend (2.3.1)
from those functions for which it is well-defined, to all of
L2(R). One way of doing this is to observe that the images
under (2.3.1) of the orthonormal basis
emn
of L2(R),
ItL
A
=
40.
x[O,
A)(
-
nA)
(
7
E
'1
e,,(x)
=
A-'/2e2T'mx/A
are well-defined, and constitute again an orthonormal
basis of L2([0, 112),
(
Uze,,)(
t,
s)
=
e-2T"ne2T'ms.
It follows that (2.3.1) defines a unitary map from
L2(R)
to
L2([0,1l2).
On the other hand, (2.3.1) can also be ex-
tended to values of
(t,
s)
outside
[0,
112.
For
f
E
L2(R), the
resulting function is in L~,,(R2>, and satisfies
(Uzf)(t+W
=
(Uzf)(t74
(
Uzf)(
t,
s
+
1)
=
e2Trt(
U,
f
)(
t,
s)
(2.3.2)
almost everywhere (ax.) with respect to Lebesgue mea-
sure on
R2.
A
rather remarkable consequence of (2.3.2) is
the following. Suppose that
f
is such that
U,
f
is continu-
ous (on
R2).
Then
U,f
must necessarily have a zero in
[0,1l2. The proof of this fact, first pointed out in [581, is
quite simple. The presentation given here is borrowed
from [59]. If
U,f
had no zero in [0,112, then logUzf
would be a univalued, continuous function on [0,1l2 ex-
tending to a continuous function in
R2
by (2.3.2). On the
other hand, (2.3.2) implies that
(logUzf)(t +l,s)
=
(logU,f)(t,s)
+257ik
(log
Uzf
) (
t
,
s
+
1)
=
(log
Uzf
) (
t
,
s
)
+
2
Tit
+
2
Til
(2.3.3)
where
k,
1
are integers, independent of
t,
s
because of the
continuity of log
U,
f.
But (2.3.3) leads immediately to the
following contradiction:
0
=
(log
U,f
)
(0,O)
-
(1%
U,f)
(
1
9
0)
+
(1%
Uzf)
(
1
,o>
-
(log
Uzf
17
1)
+
(1%
Uzf
(
19
1)
-
(log
Uzf
)(O,
1)
+
(log
Uzf
)(07
1)
-
(1%
Uzf
)(O,
0)
=
-
2n-ik
-
2n-i
-
257il+
2rik
+2n-il=
-
2rri
#
0.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
977
This proves that we started from a false premise, i.e., that
Uzf
has a zero in [0,1l2. A similar argument proves
Theorem
2.3.
The above is only one of the many proper-
ties
of
the Zak transform. For more of these properties,
and interesting applications of the Zak transform to sig-
nal analysis, we urge the reader to consult [60].
The images, under the Zak transform,
of
functions
g,,
(with
po*qo
=
27~1,
are remarkably simple. One easily
checks that, for the choice
A
=
qo,
(Uzgm,)(
t,
s)
=
e2Timse-2Ti‘n(UZg)(
t,
s).
(2.3.4)
An
immediate consequence of
(2.3.4)
is
C
I
(gmntf)
I’
=
C
I
(UZgrnn, UZf)
I’
m,n
m,n
It follows that the
g,,
constitute a frame, with frame
bounds
A,
B,
if and only if, for (t,s)E[O,1l2 a.e. (and
hence, by
(2.3.2),
for
(t,s)
E
R2
a.e.)
All2
I
I(Uzg)(t,s)
I
I
B1l2.
This is another crucial ingredient
of
the proof of Theorem
2.3,
to which we now turn.
Proof of Theorem
2.3:
Suppose that the
g,,
consti-
tute a frame, and assume also that
xg,
g‘E
L2(R).
We
want to show that this leads to a contradiction. Define
G(t,
s)
=
(U,gXt,
s).
Since the
g,,
constitute a frame, we
have
a~lG(t,s)I~
b
(2.3.5)
for some
a
>
0,
6
<m,
and for
(t,
s)
E
R2,
a.e. For com-
pactly supported
f
one finds
[U,($)]
(t,
s)
=qi/2s(~Zf)(t,s)
-q03/2Ce2.rrir‘lf(qg(s-~))
I
This shows that
xg
E
L2
implies
a,G
=
a,(U,g)
E
L;,,(R2).
Similarly
g‘
E
L~
implies
a,G
E
L;,,(R~).
If the square integrability of the partial derivatives
of
G
implied that
G
was continuous (which it does not, since
we are in more than one dimension), then the proof
would be finished. By the argument given before the
proof, inf
IC1
would then be zero, which is in contradic-
tion with
(2.3.5).
This is essentially the argument of Balian
in [HI, where the implicit assumption that
G
is continu-
ous seems to be made. Lemma
2.4,
due to
R.
Coifman
and
S.
Semmes, which we state below, shows how the
boundary conditions
(2.3.21,
together with the bounds
(2.3.51,
lead to a contradiction, without assuming continu-
ity for
G.
The main idea is to use an averaged version of
G.
This averaged function is automatically continuous,
and, if the averaging is done on a small enough scale,
close enough to
G
so
that the properties inherited from
(2.3.5)
and
(2.3.2)
still lead to a contradiction. This then
proves Theorem
2.3.
0
Lemma
2.4:
Assume that
G
is a bounded function on
R2
that is locally square integrable and which satisfies
G(t+l,s) =G(t,s)
G(t,s+l) =e2TrfG(t,s).
If both
a,G
and
d,G
are locally square integrable, then
essinf,,,,,,,
IG(t,s)l=
0.
Here the “essential infimum”
of
a measurable function
f
is defined by
essinf
f
=
inf
{A;
I{
x;
f(
x)
I
A)
I
>
0)
where
IVI
denotes the Lebesgue measure of the set
V.
This definition avoids values taken by
f
on sets
of
mea-
sure zero. For instance, for
f(x)
=
l
for
x
#
0,
f(0)
=
0,
one has inf
f
=
0,
but essinf
f
=
1.
Proof of Lemma
2.4:
This proof is rather technical; it
0
Note added
in
proof
After this paper was written,
G.
Battle produced a very elegant new proof
of
Theorem
2.3
which avoids the use of the Zak transform [69].
Battle’s paper only treats the case where the
g,,
are an
orthonormal basis (as did the original papers by Balian
and Low). His argument was extended to frames by
A.
J.
E.
M. Janssen and I. Daubechies [70].
For the critical value
po-qo
=
2~
we see thus that not
much regularity and/or decay can be expected from a
function
g
leading to a frame. This is in marked contrast
with the case
po-qo
<2~.
In that case, as shown in
Section 11-B-la, there even exist C”-functions
g
with
compact support such that the associated
g,,
constitute a
tight frame.
This critical value
po.qo
=
27r,
has a physical meaning.
As shown by Fig. l(a),
(po.qo)-l
is the density, in phase
space, of the discrete lattice of functions
g,,.
The density
(27r)-’
is nothing but the Nyquist density; it is well-known
in information theory that time-frequency densities at
least as high as the Nyquist density are needed for a full
transmission
of
information. It is therefore not surprising
to encounter this same critical value here. One encoun-
ters the same argument in quantum physics, often used in
semiclassical approximations, where a complete set
of
independent states (i.e., a set
of
linearly independent
functions in
L2(R)
whose linear combinations span a
dense subspace in
L2(R))
heuristically corresponds to a
density
(257)-’
in phase space. In other words, every state
“occupies” a “cell” of area
27r
in phase space.
For
po.qo
>
27r,
the intuition from physics or informa-
tion theory suggests that the associated phase space lat-
tice is “too loose,” i.e., that the
g,,
cannot span the
whole Hilbert space. More precisely, we expect that for
is given in Appendix B.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
978
IEEE
TRANSACTIONS
ON
INFORMATION
THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
any
g
E
L2(R), there exists at least one
f
E
L2(R),
f
#
0,
such that
(g,,,
f)
=
0
for all
m,n
E
Z.
This is indeed the
case.
If
po.qo
/27r
>
1
is rational, then the following argu-
ment, again using the Zak transform, shows how to con-
struct a function
f.
By a dilation argument we can restrict ourselves to the
case
po
=
277,
q,
=
K/L, with K, L
EN,
K
>
L
>
0.
Let
F,
G, G,,
be the Zak transforms of respectively
f,
g, g,,,
as defined by (2.3.11, where we take
h
=
1. Then
Gm,(
t,
s)
=
e28imSG
t
s
-
n
-
i3
3
For
n
=
kL
+
I,
with
I,
k
E
Z,
0
I
I
<
L, this reduces to
G
t
S--K
(7
3
G
(
t,s)
=
e2srims
-27rikK1
mn
where we have used (2.3.2). The function
F
will be
orthogonal in L2([0,112) to each
G,,
if, for all
s
~[O,ll
and for all
k,l
EZ
with
051
<
L,
cdrF(r,s)e-2"kK'G
t,s
-
-K
=
0.
(2.3.6)
i
li
We can rewrite (2.3.6) as
['Kdfe-2srikK1
K-1
G(r
+-,s--K)F(r+:,s)=O.
m1
m=O
KL
(
2.3.7)
We are thus led to the linear system
of
equations
K-1
A,,(t,s)+,(t,s)=~
OSI<L (2.3.8)
m=O
where
m
)
(2.3.9)
+,(t,s)=F
t+-
s
.
(
2.3.10)
Since the system (2.3.8) has L equations for K
>
L un-
knowns, it always has a nonzero solution, for every pair
(t,s)
E
[O,l/K)x [0,1]. The
+,(r,
s)
solving (2.3.8) can,
moreover, be chosen in L2([0,1/K)X[0,1]). One way of
doing this
is
to choose a fixed
U
E
CK,
and define
+,&,
s)
=
lim.
~~
u,(t,
s;
T),
where
u(t,s;T) =exp[-~A*(t,s)A(t,s)]u.
Clearly Ilu(t,s;
T)II*
I
llu1I2;
hence
C$=,l+,(t,
s)12
I
llu1I2.
On the other hand, since all the
A,,
are in L2([0, 1/K)X
[0,1]), the u(t,s;~) are clearly measurable in
t,s;
as
pointwise limits of measurable functions, the
4,
are
measurable too. Putting the
6,
together according to
(2.3.10) then defines a function
F
in L2([0,1I2) which is
orthogonal to all the
G,,.
Note that while
F
may be zero
a.e. for some choices of
U,
it is impossible that the
functions
F(u,)
associated with K linearly independent
vectors
U,;
.
3,
uK in
CK
all be zero a.e., since this would
mean that
A*(t,
s)A(t,
s)
>
0
a.e. in
t,
s,
which contradicts
(
"K.1
rank
[
A(t,
s)]
<
K. For appropriately chosen
U
E
CK,
the
previous construction leads thus to a nontrivial function
F
E
L2([0, 112) orthogonal to all the
G,,.
This argument does not work if
p,.
q,
/27r is irrational.
It is nevertheless still true that the
g,,
do not span
L*(R), whatever
g
in L2(rW) is chosen, even for irrational
values of po-qo/27r. The only proof that
I
know of this
fact uses von Neumann algebras; it was pointed out
to me by R. Howe and T. Steger. The proof consists
in the computation of the coupling constant of the von
Neumann algebra spanned by the Weyl operators
(W(mp,,
nq,);
m,
n
E
Z).
The coupling constant for this
von Neumann algebra was computed explicitly by
M.
Rieffel [49]; for
po.qo
>
27r it is larger than 1, which
implies that the von
Neumann algebra has no cyclic
element. This means that for any
g
E
L2(R), the closed
linear span of the
g,,
is a proper subspace
of
L2(R),
which was the desired result. Unfortunately, this proof
does not seem very illuminating from the signal analyst's
point of view.
Note added
in
proofi
Recently H. Landau [71] found
a different, intuitively much more appealing argument to
prove that the
g,,
cannot constitute a frame if
po'qo
>
27r. His proof works for all
g
which are reasonably "nice"
(decaying in both time and frequency).
This concludes what we have to say about the critical
value
(po.qo
=
277-1 in the Weyl-Heisenberg case. We
shall always assume
po.qo
I
277 in what follows.
6) Ranges for the parameters
po,
qo,
and estimates for
the frame bounds:
In the preceding subsection we have
excluded parameters
p,,
q,
for which
p,.
q,
>
277. Even
if
po.qo
I
277-, however, we do not automatically have a
frame for arbitrary functions
g.
When, for example,
g(x)
=
1
for
0
I
x
2
1,
and
g(x)
=
0,
otherwise, the
g,,
can-
not constitute a frame
if
qo>
1,
even
if
po*qo<27r.
Indeed, for
q,
>
1,
one finds that
(g,,,
f)
=
0,
for all
m,
n
E
Z
if the support of
f
c
[l, q,], independently of the
choice of
p,.
This is thus a case where an inappropriate
choice of
q,
excludes the possibility of a frame, for all
values of
p,.
The theorem below gives sufficient conditions on
g
and
q,
under which this cannot happen, i.e., there always exist
some
po
>
0
(in fact, a whole interval) leading to a frame.
Theorem
2.5:
If
1)
m(g;q,)=
essinf
~lg(x-nq,)12>0
(2.3.11)
2)
M(
g
;
q,)
=
esssup
I
g(
x
-
nq,)
l2
<w
(2.3.12)
and
3) sup[(l+s2)'I+€"2p(s)]
=~,<w
forsomec>~
where
p(s)=
sup
c
Ig(x-nq,)IIg(x+s-nq,)I
x
E[O,quI
n
x~[O,q~l
n
S€R
x
E
[o,
4,,1
n
E
L
(2.3.13)
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREVUENCY LOCALIZATION AND SIGNAL ANALYSIS
979
then there exists a
Pi
>
0
such that
Theorem
2.6:
Assume that
(2.3.11), (2.3.12), (2.3.13)
are
satisfied. Define
Vp,
E
(0,
Pi)
:
the
g,,
associated with
g
,
P,
,
qo
I
I/’
1
p;=inf
po
p
-k
P
--k
2Tm(g;qo)
.
[
lkIl[
(:
)
(
:
)]
are a frame
VS
>
0:3p, in [Pi,
Pi
+
61
such that the
gm,
associated to
g,
p,,
q,
are not a frame.
Proofi
see Appendix C.
0
The conditions
(2.3.11)-(2.3.13)
may seem rather tech-
nical. They are, in fact, extremely reasonable. Condition
(2.3.11)
specifies that the collection of
g
and its translates
should not have any “gaps.” This already excludes the
example given at the start
of
this subsection. The condi-
tions
(2.3.121, (2.3.13)
are satisfied
if
g
has sufficient
decay at
03,
in particular, if
Ig(x)l
I
C[1+ x21-3/2.
Note that both
(2.3.11)
and
(2.3.12)
are necessary con-
ditions. If
(2.3.11)
is not satisfied, then for every
E
>
0
one
can find a nonzero
f
in
L2(rW)
such that
C
1
(gm,,f>
1’
I
~II~II~
m,n
which means there exists no nonzero lower frame bound
A
for the
g,,.
Similarly there exists no finite upper frame
bound
B
for the
g,,
if
(2.3.12)
is not satisfied.
Remarks
1)
At the end of the preceding subsection we showed
that the
g,,
can constitute a frame only if
po-qo
I
277.
Hence necessarily
Pi
I
2~/q,.
2)
The set
{po;
the
g,,
associated to
g,p,,q,
consti-
tute a frame) with
g
and
q,
fixed need not be
connected. It is possible that this set contains values
of
po
larger than
Pi.
An
example is given by the
following construction. Let
4
be a
C”
function with
support
[0,
1/31
such that
141
has no zeros in
(0,1/3).
Define
g
by
0,
YIO
4(Y),
g(~)=
4(~-1/3), 1/3~~12/3
0
I
y
I
1/3
+(y-2/3), 2/3_<y11
I
0,
y2l.
Take
q,
=
27r.
Then, since support
2
=
[O,
11,
c
I
(
gmn
9
f
)
I
=
/dy
c
lg(
Y
-
)
I
I
fi
Y
)
I
m,n
m
This implies that the
g,,
constitute a frame
if
and
only
if
infC,Ig(y
-
mp0>l2
>
0.
Consequently
PO’
=
1/3,
while the set
of
all
po
leading to a frame is
(0,1/3)U(1/3,2/3).
For reasonably smooth
g
with sufficient decay at
m,
the
constants
m(g;
q,),
M(g;
q,)
and the function
P(s)
can
easily be computed numerically. These constants are use-
ful in estimations of the frame bounds
A,B,
as the
following theorem shows.
Then
p;
I
Po’,
and for
0
<
po
<p&
the following esti-
mates for the frame bounds
A,
B
holds
Proof
see Appendix C.
U
These bounds for
A
and
B
can be improved by the
following observation. If the
g,,(x)
=
eimpoxg(x
-
nq,)
constitute a frame, then
so
do the
where
2
denotes the Fourier transform of
g.
It follows
that
A2
(
gmnIA
(
C)
=
e-ins(~Li(
c
-
m~,)
9
(2.3.14)
B_<
(2.3.15)
Here
M($;p,),
m(g;pO)
and
b(s)
are the obvious exten-
sions of the quantities in
(2.3.111, (2.3.121,
and
(2.3.13).
For instance,
b(s)
=
SUP
C
16(5+mPO)Ilg(5+s+mP,)l.
5
E
[O,
pol
m
E
.Z
Similarly, one has the following better lower bound for
pi,
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
980
IEEE
TRANSACTIONS
ON
INFORMATION
THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
0.4
0.3
0.2
0.1
0
-0.1
C)
Examples
i)
The
Gaussian case
In this case
g(x)
=
T-1/4e-~2/2
(2.3.17)
This is the basic function for the so-called “canonical
coherent states” in physics
151.
It is also the basic function
chosen by Gabor
[l]
in the definition of his expansion. In
the notations used in this paper, Gabor’s approach
5
-
-
0
-
-5
0.20
I
I
-0.05
I
-10
-5
0
5
10
(a)
0.3
0.2
0.1
0
-0.1
-
10
-5
0
5
(b)
amounts to writing an expansion with respect to the
g,,
associated to
g,
po,
qo,
where
po.
qo
=
277.
This choice
seems very natural from the point of view of information
theory, since it corresponds exactly to the Nyquist density.
However, since both
xg
and
g’
are square integrable in
this case, Theorem
2.3
tells
us
that the
g,,
cannot
possibly constitute a frame. In fact, the Zak transform
U,g
of
g
(see Section 11-C-la) can be constructed explic-
itly in this case; it is one of Jacobi’s theta-functions, and it
-0.2
I
-
10
-5
0
5
10
1
.o
0.5
0
-0.5
-10
-5
0
5
(e)
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
981
DAUBECHIES: THE WAVELET TRANSFORM. TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
has a zero in (1/2,1/2) [21, [31, [601, [631. The operator
U
of Section 11-A is unitarily equivalent with multiplication
by
IUzg12
on
L2([0,
112),
and is therefore one-to-one, but
it has an unbounded inverse, i.e.,
~~~~EL~(R)II~II-~
C
I
(hmn>f)
1'
=
0.
m,n
One can still write an expansion of type
f
=
C
gmn(grnn,f)
m,n
but this expansion has, in general, bad convergence prop-
erties because
g
L2(iw)
(since
U,g
=
U,(T-'g)
=
lUzgl-2Uzg
has a pole at (1/27 1/21, and is therefore not
in Lz([0,112)). It is this fact that makes the expansion
associated to the Gabor wave functions unstable [2], [3],
[601. The function
g
was explicitly constructed in [2]; it
turns out to be discontinuous as well as nonsquare-inte-
grable (see Fig.
4(f)).
Explicit computation of
2
(via the
Zak transform), for
pO
.=
q,,
=
G,
leads to [2]
g(x>
=
cexz/2
(
-
1)ne-T(n+
I/2?
n
+
1/2
z
x/&
where
C
is a normalization constant.
For
g
Gaussian, as in (2.3.17), the fact that the
g,,,
do
not span
L2(R)
if
pO'qi,
>
27r, has been known for quite a
while [611, 1621. The proofs in [611, 1621 use entire function
techniques. These techniques do not work, however, for
non-Gaussian
g.
Our first table of numerical results, for Gaussian
g,
lists
pf,,
for different values
of
qo
(see Table I). It turns
out that
ph
is always very close to 27r/q,; for this reason
we have tabulated (27r/qi,.p6)- 1, rather than
p6
itself.
The difference (27/q0.p6)- 1 is largest for
q(,
=
G,
where it is about 4
X
lop3.
TABLE
I*
1
.o
6X
lo-'
1.5
3~10-~
2.0
2x
10-~
3.0
4x
3.5 2x
lo-'
4.0 8X
2.5
4X
lo-'
*The deviation,
for
g(x)=
~-'/~exp(-
x2/2),
of the esti-
mated value
ph
from the opti-
mal value
2~/9,)
(see text).
Note that
Pi
_<
27/q,. The numerical results show
therefore that in this case the estimate
pf,
is remarkably
close to the true critical value
Pi.
In fact they suggest the
conjecture that
Pi
=
27/q0, for all
qo
>
0,
in this case.
I
believe that this conjecture holds for all positive functions
g
with positive Fourier transform.
Next we list the estimates (2.3.14) and (2.3.15) on the
frame bounds for a few values of
qil,
po
<
ph.
We also
tabulate the corresponding B/A, and
r
=
(B/A
-
I
l)/(B/A
+
1). This parameter measures how snug the
frame is, i.e., how close it is to a tight frame; as explained
in Section
11-A,
this parameter is essential
if
one wants to
apply the inversion formula as indicated in Section 11-A.
We have grouped together different values of
qo,po
cor-
responding to the same value of
qo.po.
If
qo.po
=
27/k,
with
k
integer, then a different method, based on the Zak
transform, enables
us
to write explicit, exact expressions
for the frame bounds
A
and B. With
U,
defined as in
Section 11-C-la (see (2.3.Q with
A
=
qo),
one finds indeed
that, for
m
E
Z,
m
=
m'k
+
r,m', r
E
Z,
0
I
r
<
k,
(
Uzgmn
1
(
t,
s
1
=
(
Uzgm'k
+r
n
1
(
t,
s
1
-
e2rrirn/ke-2~irn
2~im's
-
e
(Uzg')(t,s)
where we have used
po
=
27r/q,, and where
g(x).
g'(
x)
=
pW,,/k
Hence
(U,g')(t,s)=(U,g)
t--s
.
(
I)
This is entirely similar to computations made in Section
11-C-la; see also [451. Consequently, as in Section 11-C-la
(see also [161, [45])
which implies
To find
A
and B, in the case where 27r/(p,.q,) is an
integer, it suffices therefore to compute
Uzg
and these
two extrema.
In Table I1 next we list the estimates, given by (2.3.141,
(2.3.15) for
A,
B, B/A and
r,
for a few values of
qo,
in
the cases
po.qo
=
~/2, 3x/4,
T,
37r/2, and 1.97. In the
cases
po'qo
=
7r/2 and
7r
we also list the exact values for
A,
B, denoted by
Aexact,
B,,,,,. For values of
po
close to
the critical value 27r/q0 (see the case
qo'po
=
1.97 in
Table I), the ratio
B/A
becomes very large, as was to be
expected. The convergence
of
the formula for
2,
mea-
sured by
r,
will be very slow. For
qo
=
2.0,
po
=
7/q0
=
~/2, the ratio
r
is already of the order of 0.2, while
qo
=
1.5,
po
=
7r/3,
qopo
=
7/2 leads to
r
=
0.025. In the
latter case a few terms will suffice to obtain an accuracy
of
is the computation of
2.
This shows that very
good frames can be obtained with lattice spacings that are
not very small.
In the two cases where the exact values of
A,
B can be
computed by other means
(qo.po
=
7/2 and
qo*po
=
71,
the estimates for
A
and B, as calculated from (2.3.14) and
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
982
IEEE
TRANSACTIONS ON
INFORMATION THEORY, VOL.
36,
NO.
5,
SEPTEMBER
1990
TABLE
I1
VALUES FOR
THE
FRAME
BOUNDS
A,
B,
THEIR
RATIO
B/A,
AND
THE
CONVERGENCE
FACTOR
r
=
(B/A
-
l)/(B/A
+
l),
FOR
THE
CASE
g(x)
=
P-'/~
exp(
-
x2/2),
FOR
DIFFERENT
VALUES
OF
q0.
po*
0.5
1.203
1.221 7.091
7.091
5.896 0.710
1.0
3.853 3.854
4.147
4.147
1.076 0.037
1.5
3.899 3.899
4.101
4.101
1.052 0.025
2.0 3.322
3.322 4.679
4.679
1.408 0.170
2.5 2.365
2.365 5.664
5.664
2.395 0.41 1
3.0
1.427 1.427
6.772 6.772
4.745 0.652
4tr'Po
=
3r/4
40
A
B
B/A
r
=(B
-
A)/(B
+
A)
1.0 1.769
3.573
2.019 0.338
1.5 2.500 2.833
1.133 0.062
2.0 2.210 3.124
1.414 0.172
2.5 1.577
3.776
2.395 0.41 1
3.0 0.951 4.515
4.745 0.652
4t)'PtI
=
r
9[)
A
Acracl
B
B,,,,,
B/A
r=(B-
A)/(B
+
A)
1.0 0.601 0.601 3.546
3.546
5.901 0.710
1.5
1.519 1.540
2.482 2.482
1.635 0.241
2.0 1.575 1.600
2.425
2.425
1.539 0.212
2.5
1.172 1.178
2.843 2.843
2.426 0.416
3.0 0.713 0.713 3.387
3.387
4.752 0.652
qtl~pt,
=
3712
411
A
B
B/A
r
=(B
-
A)/(B
+
A)
1.0
0.027
3.545 130.583
1.5
0.342
2.422 7.082
2.0 0.582 2.089
3.592
2.5 0.554 2.123
3.834
3.0 0.393
2.340 5.953
3.5 0.224
2.656
11.880
4.0 0.105 3.014
28.618
90
'Po
=
1.9r
911
A
B
B/A
0.985
0.753
0.564
0.586
0.712
0.845
0.932
close to a multiple
of
the unit operator. Consequently
g
=
U-'g
is very close to a (scaled) Gaussian. For increas-
ing
po
=
qo,
several things happen to
g.
The decrease
of
both frames bounds
A
and
B,
which reflects the decrease
in the "oversampling ratio"
27r(poqo)-',
causes the am-
plitude of
g
to increase. Moreover, the frame becomes
less and less snug (for
po
=
qo
=
(1.97r)'12,
one even has
r
>
0.91,
causing to deviate more and more from a
Gaussian. In all these examples (Figs.
4(a)-4(e)),
the
function
g
remains square integrable, however. One can
even show that it remains
C",
with fast decay. This is no
longer the case
if
po
=
qo
=
(2~)"~.
In this limiting case,
where the
g,,
no longer constitute a frame, one can still
construct
=
U-'g,
but, as previously shown, is no
longer in
L2.
This singular
g'
was first plotted by
Bastiaans
[2];
we have replotted it here in Fig.
4(f).
One
clearly sees how the regular
2,
for lower values of
po-qo,
approaches the singular limiting function as
po
=
qo
in-
creases towards
(27r)'12.
In this
case
rn(g;q,)
and
M(g;q,)
can be calculated explicitly.
One finds
ii)
The
exponential case:
We take
g(x)
=
4g;qo)
=(sinhqo)-'
M(g;q,)
=cothq,.
The function
p
cannot be written in closed analytic form.
In Table 111 we list
p;
for a few values of
qo;
we also list
again
27r/(qo.p;)-l,
which is much less close to zero
in this case. In Table
IV
we list
A,
B,
B/A
and
r=
(B/A
-
1)/(
B/A
+
1)
for several values
of
qo,
po.
Again
we have grouped together those pairs
qo,po
with the
same value of
po.
qo;
in the cases
po.
qo
=
T
/2,
po.
qo
=
7r/4
we compare the estimates with the exact values.
1.5 0.031
2.921
92.935 0.979
2.0 0.082
2.074
25.412 0.924
2.5 0.092 2.021
22.004 0.913
3.0
0.081
2.077
25.668 0.925
3.5 0.055 2.218
40.455 0.952
4.0
0.031
2.432 79.558
0.975
TABLE
111
THE ESTIMATED
VALUES
p&
AND
THEIR
DEVIATION
FROM
2r/q,,
FOR
g(x)=
e-'x'
4n
Pk
2r/(qn.p:)-
1
*Where possible
(qo.po
=
r/2,
qO,ppo
=
P)
the estimates for
A,
B
are
compared with the exact values (computed via the Zak transform; see
text)
(2.3.151,
turn out to be remarkably close to the true
values, giving deviations of at most a few percent on
A,
and less than
0.1%
on
B.
In the next example we shall
find similar orders of magnitude for the deviation of our
estimates for
A,B
with respect to the exact values. The
formulas
(2.3.14)
and
(2.3.15)
seem thus to give quite
good results, despite the rather brutal estimating methods
used.
For every one of the values of the product
qo*po
in
Table I1 we have also computed by means of the
inversion formula
(2.1.5).
These functions
g'
are plotted in
Fig.
4,
for the choice
qo
=
po.
For
po
=
qo
=
(7r/2)'I2,
we know, from Table
11,
that
the frame is snug
(r
2:
0.02
in this case), i.e., that
U
is
very
~
0.5
1
.0
1.5
2.0
2.5
3.0
3.5
4.0
5.32 1.36
2.99 1.10
2.52 0.66
2.21 0.42
1.92 0.30
1.68 0.25
1.48 0.22
1.33 0.17
In the two cases, in Table
IV,
where the exact values of
A,
B
can be computed via the Zak transform (for
qo*po
=
7r/2
and
qo*po
=
7r/4),
we see again that the estimates
for
A
and
B
given by
(2.3.14)
and
(2.3.15)
are remarkably
close to the exact values. The error on
B
is negligible,
and the error on
A
does not exceed a few percent. Note
also that frames based on the exponential used here are
much less ''snug" than Gaussian frames (compare e.g.,
the value of
r
for
qo
=
1,
po
=
~/2,
which is
0.399
in the
present case, but
0.037
for a Gaussian).
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANAI-YSIS
983
TABLE
IV
VALUES
FOR
THE
FRAME
BOUNDS
A,
B,
THEIR
RATIO
B/A,
AND THE
CONVERGENCE
FACTOR
r
=
(B/A
-
l)/(B/A
+
1).
FOR
THE
CASE
g(x)
=
exp(
-
Ixl),
FOR
DIFFERENT
VALUES
OF
q,,,
prr*
~
1.0 2.600
2.724
6.056 6.056
2.330 0.399
1.5 2.665
2.692 6.781
6.781
2.544 0.436
2.0 2.179
2.190
8.326 8.326
3.821 0.585
2.5 1.648
1.657 10.140
10.140 6.152
0.720
3.0
1.197 1.206
12.060 12.060
10.074 0.819
qo‘po
=
37/8
90
A
B
B/AQ
r
=(E
-
A)/(B
+
A)
0.5 2.014
8.873 4.405
0.630
1.0 4.203
7.339
1.746 0.272
1.5 3.724 8.872
2.382 0.409
2.0 2.938 11.068
3.767 0.580
2.5 2.204 13.514
6.133 0.720
3.0 1.597 16.080
10.068 0.819
40.Po=a/4
qo
A A,,,,,
B B,,,,,
B/A
r
=(B
-
A)/(B+
A)
1.0
6.757 6.766 10.554
10.554
1.562 0.219
1.5 5.634
5.645 13.259
13.259 2.353
0.404
2.0 4.412 4.426 16.597 16.597
3.762 0.580
2.5 3.306 3.322 20.271
20.271
6.132 0.720
3.0 2.396 2.413 24.119 24.119
10.068 0.819
*Where possible
(qo.pI,
=
n/2, ql,’po
=
a/4)
the estimates for
A,
B
are compared with the exact values (computed via the Zak transform;
see text).
2)
The Wavelet Case:
a)
Ranges for the parameters
a,,
bo-
Estimates for the
frame bounds:
In Section 11-B-lb) we construct tight
frames for arbitrary choices of
a,
>
1,
b,
>
0.
This shows
that there exists no absolute,
a
priori
limitation on
a,,
b,
-values leading to frames, unlike the Weyl-
Heisenberg case, where
po.qo
I
27 is a necessary condi-
tion (see Section 11-C-la)). This freedom in the choice of
aO,b,
is deceptive, however, because of the behavior of
wavelet frames under dilations. If the
h,,,
based on
h,
with parameters
a,,
bo,
constitute a frame, then
so
do the
hy;,,,
based on
h,(x)
=
y’I2h(yx),
with frame parame-
ters
a,,y-’b,.
This explains, at least partially, why a
frame can be constructed for
any
pair a,,b,.
To
elimi-
nate this dilational freedom, let us restrict our attention,
in the pre:ent discussion, to frames such that
llhll=
1
and
jdk
lkl-’Ih(k)l*
=
1.
Under this restriction, one might
hope again that there exists a critical curve
b$a,)
sepa-
rating the “frameable” pairs from the “nonframeable,”
with the orthogonal bases corresponding to the curve
itself. This was the situation for the Weyl-Heisenberg
case. It turns out however that this picture is not true in
the wavelet case. At the end
of
this subsection, in Theo-
rem 2.10, we establish the following counterexample. We
take
Y.
Meyer’s basic wavelet
I,/J,
and look at the
i,!~,,,~~~,
a
family of wavelets generated from
I,/J
with
a,=
2,
b,
arbitrary. For
bo=
1, these wavelets constitute an or-
thonormal basis [31]. If there existed a nice critical curve
bh(a,)
separating frameable and nonframeable values,
then we would expect that the
i,!J,,,n;h,,
would not be a
frame for
bo
>
1
(“not enough” vectors), and might be a
frame consisting of nonindependent vectors for
b,,
<
1
(“too many” vectors). It turns out, however (see Theorem
2.10), that there exists
E
>
0
such that, for all values of
6,)
in
(1
-
E,
1
+
E),
the associated
i,!J,,:b,,
constitute a basis
for
L*(R).
This baffling fact shows that the concept of
“phase space density,”
so
well-suited for Weyl-Heisen-
berg frames, is not well adapted to the wavelet situation.
For the wavelet case this is all we have to say in answer
to question 11, as formulated at the start of Section 11-C.
The following theorem addresses question 21, i.e., the
determination
for
a given function
h,
of a range
R
such
that the
h,,
are a frame for all choices
(a,,
bo)
E
R.
The
formulation of this theorem is very similar to Theorem
2.5, and
so
is its proof.
Theorem
2.7:
If
1)
m(h;a,)=
essinf
Ih(a;;,x)I*>O
(2.3.18)
Ixlr[l,a,,l
,€L
2)
M(h;a,)=
esssup
Ih(arx)l*<m
(2.3.19)
and
Ixl~[1,a,,l
rnEZ
where
P(s)=
sup
~i(a;;,x)~~i(a~x+s)
lxl€[l,a”l
rnEZ
Then there exists a
B,“
>
0
such that
Vb,
E
(0,
B,“)
:
the
h,,
associated to
h
constitute a frame,
(2.3.20)
.
(2.3.21)
a,,b,
VS
>
0
Ab,
in
[
B;,
Bi
+
S]
such that the
g,,
associated to
h,
a,,
b,,
are not a frame.
Pro08
see Appendvc
C.
0
Remarks:
1)
The conditions (2.3.181, (2.3.19) are again necessary
conditions.
If
(2.3.18)
is not satisfied, then
inf,,,2
llfll~*~,,,l(h,,,
f)I2
=
0,
which excludes
the existence of a nonzero lower frame bound. Simi-
larly (2.3.19) is necessary for the existence of a finite
upper frame bound.
2) The range
R
of “good” parameters, i.e., the set of
(a,,
bo)
such that the
h,,,
associated to
h,
a,,
bo,
constitute a frame, need not be connected. It is
possible to construct functions
h
such that, for fixed
b,,
there exist
a,,,
<
a,,*
<
for which the
h,,
associated with
h,
a,,j;
b,
constitute a frame
if
j
=
1
or 3, but do not if
j
=
2. (The construction is similar
to the one given for the Weyl-Heisenberg case. See
Remark 2, following Theorem 2.5.)
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
984
IEEE
TRANSACTIONS ON
INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
3)
Theorem
2.7
is pnly useful for choices of
h
for which
the support of
h
contains negative as well as positive
can be sharpened. The following corollary is due to Ph.
Tchamitchian.
frequencies. In some cases one prefers to work with
functions
h
with support
h
c
R,.
Functions with this
property are also called "analytic signals," because
they extend to functions analytic on a half-plane.
Theorem
2.9:
Choose
a,=
2.
Under the same condi-
tions as in Theorem
2.7,
the following estimates for the
frame bounds
A,
B
hold,
{h;,,;m,nEZ,
h+=h,
h-=h*)orof{h',"A;
m,nE
I=O
See e.g.,
[681.
The frame to be used then consists
of
Z,
A
=
1,2
h"'
=
&
re
h,
h")
=
&
im
h).
For these
frames the conclusions of Theorem
2.7
hold under
very similar conditions. The only changes to be made
concern the definitions of
m(h;
a,),
M(h;
a,)
and
B(s).
In each of these definitions, the condition
(2.3.25)
I=O
1x1
E
[l, a,]
should be replaced by
x
E
[l,~,].
As in the Weyl-Heisenberg case (Theorem
2.51,
the con-
ditions
(2.3.18)-(2.3.20)
may seem very technical. They
are however very easy to check on a computer. Good
estimates for
m(h;a,),
M(h;a,)
and
p(s)
lead again to
useful inequalities for the frame bounds
A
and
B.
-pI
-
-(2/+1)]]"*} (2.3.26)
(t
Theorem
2.8:
Under the same conditions as in Theo-
where
rem
2.7,
the following lower bound for
B,'
holds
I
Pro08
See Appendix C.
0
Note that the estimates in Theorem
2.9
use some of the
phase information contained in
fi,
which is completely
lost in the estimates in Theorem
2.8.
It is therefore to be
expected that the estimates
(2.3.23, (2.3.26)
are
,a
signifi-
cant improvement
(2.3.231, (2.3.24)
for complex
h.
This is
illustrated most dramatically by applying both pairs of
at the end of Section 11-B-lb)). For
h
=
@,
with
@
defined
by
(2.2.71,
one finds
C,l@(2"y)I2
=
1,
p(27r)
=
p(-277)
=
1/2, p(47)=p(-4~)=1/2,
and
p(k2~)=0
if
lkl23,
bn
k=l
[
(
1
(
]]"2)'
hence
c~=1[p(2~k)p(-2~k)]1/2
=
1.
Applying Theorem
2.8
we therefore find
A
2
-
1,
B
I
3.
This means that if we had only the bounds
(2.3.231,
(2.3.24)
to go by, we wouldn't be able to recognize that
the
@mn
constitute a frame. Since, for
a,
=
2
and
bo
=
1,
the
@,,,
do in fact constitute an orthonormal base, this is
a rather poor performance. Calculating
PI
we find that
>m(h;a,)
.
(2.3.22)
i
For
<
'0
<
'69
the
foilowing
estimates
for
the
frame
estimates to the basic wavelet in
y.
Meyer's basis (defined
bounds
A,
B
hold
A>-
m(h;a,)-2
p
-k
p
--k
(2.3.23)
2=
i
BI-
k=l
(2.3.24)
p,(2~k)
=
0,
for all odd
k.
Pro08
see Appendix C.
0
Remark:
The proof in Appendix
C
applies for the case
where both
R+
n
support
fi
and
iw-
n
support
fi
hav:
nonzero measure. If this is not the case, e.g., if support
h
c
R+,
and the frame considered is either
{h;,lm,n
E
Z,
h+=h,h-=h*)or{h',"~lm,(nEZ,
A=1,2,h("=&reh,
=
fi
im
h}
see Section 11-B-lb)), then the definitions
of
m(h;
a,,),
M(h;
a,),
p(s)
have to be slightly changed
(the restriction
1x1
E
[l,
a,]
is replaced by
x
E
[l,
a,]-see
Remark
3
following Theorem
2.71,
and the same formulas
(2.3.231, (2.3.24)
apply.
In most practical examples the dilation parameter
a0
is
equal to
2.
In this case the estimates
(2.3.23)
and
(2.3.24)
The estimates in Theorem
2.9
thus lead to
A
2
1,
B
I
1,
or equivalently to the optimal estimate
A
=
B
=
1.
(Note
that this automatically proves that the
@,,
constitute an
orthonormal basis, since
11@,,,11
=
ll@ll=
1.
We showed in
Section 11-A that a tight frame with frame constant
1,
consisting of normalized vectors, necessarily is an or-
thonormal basis.) Since the phase factor in the definition
of
Y.
Meyer's basic wavelet
(2.2.7)
is essential for the
@,,
to constitute an orthonormal basis (see e.g.,
[311),
it is
natural that the phase-dependent estimates
(2.3.25),
(2.3.26)
perform much better than the phase-independent
estimates
(2.3.231, (2.3.24)
in this case. Using Theorem
2.9
one can prove the result we just announced, i.e., that
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
985
the wavelets
+hrn,,,
associated with
Y.
Meyer’s
$,
and with
a,
=
2,
b,,
arbitrary, still constitute a basis for
b,
#
1,
16,)
-
11
<
E,
for some
E
>
0. The following Theorem was
proved in collaboration with Ph. Tchamitchian.
Theorem
2.10:
Let
$
be the function defined by (2.2.7).
Then there exists
E
>
0
such that the
$rnn;bl,,
constitute a basis for
L2(R),
for any choice
bo
E
(1
-
E,
1
+
E).
Proofi
See Appendix C.
0
This result is quite surprising: it shows, as pointed out at
the start of Section 11-C-2, that it is not always safe to
apply “phase space density intuition” to families of
wavelets.
Remark:
It follows from the proof that
E
can be esti-
mated explicitly, from computations
of
the frame bounds
A,
B,
as given by (2.3.25), (2.3.26) on the one hand, and of
Corollary
2.11:
Let
h’;
.
.,
hN-’
be
N
functions satis-
fying the conditions (2.3.181, (2.3.19), and (2.3.20). Define
m(h”;..,hN-l;a,)=
essinf
CI~J(~;;~X)I~
N-I
IxlE[I,a,,l
j=()
m
(2.3.27)
N-1
~(h”;..,h~-’;a,)=
esssup
c~ij(a;;’x)~’
p’(s)=
sup
IAl(a;;x)l/6’(a;;’x+s)I.
Ixl~[l,a~J
j=o
m
(2.3.28)
lxlE[1,a,,l
tntz
(2.3.29)
Choose
b,
such that
N-l
m
1
/2
j=O
k=l
<
m(h”;
. .
,
hN-l;
a,).
Then the
(h;,,;
rn,
n
E
Z,
j
=
0,.
. .
,
N
-
1)
constitute a
frame. The following estimates for the frame bounds
A
and
B
hold,
on the other hand. This estimate for
E
depends, of course,
on the choice for the function
v
(see (2.2.7)). For the (non
C”)
choice
4x1
=
x
if
0
I
x
<1,
v(x)
=
0 otherwise, one
finds
E
>
0.02. The
$,,,n,bll
remain a frame for
b,
I
1.08 in
this case.
In many practical examples
fi
decays very fast, and is
real. In those cases the differences between estimates
using
p
(i.e., (2.3.231, (2.3.24)) or
pl,
(i.e., (2.3.2.51, (2.3.26))
are very small, and myh less dramatic then for
Y.
Meyer’s
wavelet
$.
In fact,
if
h
is positive (e.g., the Mexican hat
function, the 8th derivative of the Gaussian, the modu-
lated Gaussian,
.
s
:
see the next subsection) the esti-
mates using
p
perform better than those using
PI,
as can
easily be checked directly by the formulas (2.3.231, (2.3.241,
and (2.3.29, (2.3.26).
As already mentioned above, most practical applica-
tions use
a,
=
2. This choice makes numerical computa-
tions much easier since
it
means that the translation steps
b,,.2rn (see Fig.
l(b)),
for two different frequency levels
m,
>
m2,
are multiples of each other. It also makes the
different frequency levels correspond to “octaves.” On
the other hand one likes to use fyctions
h
with fairly
concentrated Fourier transforms
h,
correspondinng to a
good frequency resolution. This means that Crnlh(2”x)12
is bound to have rather large oscillations; since then
m(h;2)
is
much smaller than M(h;2), this leads to high,
and therefore unpleasant values of
B/A.
This can be
avoided by the use ocseveral functions
h’,
chosen
so
that
the minima of ACmlhJ(2rnx)12 are compensated by the
maxima of
C,,,lh”(2’”~)1~,
for some
j’# j.
This is made
explicit by the following corollary of Theorem 2.7.
.[PI(
?k)pJ(
-
Ek)]”’]
(2.3.30)
N-1
m
j=O
k=l
Po
*[@I(
$k)pl(
-gk)]”2].
(2.3.31)
Proofi
The proof is a simple variant on the proof of
Theorem 2.8.
0
In the special case where
a,,=
2, one can,
of
course,
replace
p’
in (2.3.301, (2.3.31) by
pi,
with
pi
defined as in
Theorem 2.8, for
j
=
0;
.
.,
N
-
1.
Then the sums over
k
#
0 also have to be replaced by sums over only odd
k.
The number
N
of
functions used is called the number
of
“voices” per octave [28]. In numerical calculations
N
=
4 seems to be a satisfactory choice.
In practice one often chooses the
h”; .
.,
hN-l
to be
dilated versions of one function
h,
i.e.,
hJ(
x)
=
2-j/Nh(2-’/Nx),
j
=
0;
. .
,N
-
1.
(2.3.32)
The phase space lattice corresponding to the
{hAn;
m,n
E
Z,
j
=
0;
.
.,
N
-
1)
is the superposition of
N
lattices of
the type depicted in Fig. l(b), shifted with respect to each
other in frequency. Fig.
5
shows such a lattice, for the
case
N
=
4, and for
a,
=
2.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
986
IEEE
TRANSACTIONS
ON
INFORMATION
THEORY, vol..
36,
NO.
5,
SEPTEMBER
1990
.......
........
........
........
........
......
........
*
-
*
........
........
........
........
......
......
.
ko
k::::::
‘I’
i
1
f
Remark:
Note that the
h’,
constructed by dilations from
one function
h
as in (2.3.321, do not have the same
,!,*-normalization,
IlhJllL~
=
2-J/2N
IlhllL2.
This change in
normalization compensates for the fact that the phase
space lattice in Fig.
5
is “denser” than the corresponding
lattice (see e.g., Fig. l(b)) would be for the same basic
wavelet
h,
but with
a,
=
2’”, and with only one function
(namely
h1
per dilation step (instead of
N,
as in Fig.
5).
b)
Examples:
We illustrate the different bounds with
several examples. In practice, it is by far preferable to use
a,
=
2,
rather than noninteger values. We have therefore,
in all our examples, restricted ourselves to
a,
=
2, and
introduced several voices (see Corollary 2.11). The differ-
ent voice-functions
hJ
are always obtained, in these exam-
ples, by dilation
of
one given function
h
(see (2.3.32)).
i)
One cycle
of
the sine-function:
In this case we take
10,
otherwise
The Fourier transform of
h
is given by
fi
sinyr
h(
y>
=
-i-
T
1-y2’
TABLE
V-A
FRAME
BOUNDS
FOR
WAVELET
FRAMES*
N=l N=2
-
~
bo/r
A B B/A
bo/r
A
B B/A
~ ~
0.25 4.038 8.409
0.50
1.838 4.386
0.75 1.412 3.007
1.00
0.585
2.527
1.25 0.337 2.152
N=3
-
bn/r
A
B
~
2.082 0.25 11.950 16.294
2.387
0.50
5.711 8.411
2.634 0.75 3.629 5.785
4.323 1.00 2.410 4.651
6.380 1.25 1.709 3.939
1.50 0.999 3.708
1.75 0.556 3.479
2.00 0.202
3.328
N=4
-
B/A
bn/r
A B
1.364
1.473
1.594
1.930
2.305
3.713
6.259
16.473
0.25 20.035
0.50
9.655
0.75 6.185
1.00 4.230
1.25 3.050
1.50 2.033
1.75 1.313
2.00 0.736
24.331
12.528
8.603
6.861
5.823
5.361
5.025
4.810
1.214 0.25
1.298
0.50
1.391 0.75
1.622
1
.oo
1.909 1.25
2.637
1
SO
3.828 1.75
6.539 2.00
27.986
13.598
8.687
6.042
4.431
3.076
2.031
1.261
32.500
16.645
11.475
9.080
7.666
7.005
6.610
6.300
1.161
1.224
1.321
1.503
1.730
2.278
3.255
4.998
*Based
on
the function
h(x)
=
{
r-II2
sin
x
1x1
I
r
The dilation parameter
a,
=
2 in all cases; N
is
the number of “voices”
(see text).
0,
otherwise
ii)
The Mexican hat:
The Mexican-hat function is the
second derivative of the Gaussian (up to a sign),
2
h( x)
=
-r-’/4(
1
-
x2)e-X2/2
6
6
2
h(
y)
=
-r-1/4y2e-~2/2.
The graph
of
h
looks
a bit like a transverse section
o,f
a
Mexican hat (see Fig. 2(b)), whence the name. Since
h
is
positive, the formulas using
p
rather than
PI
are more
effective here. The same will be true in
our
next exam-
ples. Table
V-B
lists the estimates for the frame bounds
A,B
and their ratio, for a few values of the translation
parameter
bo,
and of
N,
the number of voices.
iii) The eighth deriuatiue
of
the Gaussian:
Functions
like the Mexican hat and higher order derivatives of the
Gaussian are useful in applications of the wavelet trans-
form
to
edge detection (see, e.g., [27]). Table
V-C
lists the
estimates for the frame bounds
A,B
for wavelets based
on the eighth derivative of the Gaussian,
-
405x2
+
90)
1
/2
T-1/4
x
-y2/2
Since this is an oscillating function, one suspects that
the formulas analogous to (2.3.301, (2.3.311, but using
PI
~(y)=(z)
ye
.
rather than
p,
will perform better than the P-formulas.
This turns out to be true. Table
V-A
lists the estimates
for the frame bounds
A,B
and their ratio, for a few
values of
b,,
and of
N,
the number of voices.
This is a typical example of a function where, with
a,,
=
2
fixed, the introduction of several voices is necessary. For
N=
1
(i.e., only one voice, corresponding to the phase
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES:
THE
WAVELET
TRANSFORM,
TIME-FREQUENCY
LOCALIZATION
AND
SIGNAL ANALYSIS
987
TABLE V-B
FRAME BOUNDS
FOR
WAVELET FRAMES*
N=l N=2
bo
A
B
B/A
b,
A
B
B/A
-
-
0.25 13.091 14.183 1.083
0.50 6.546
7.092 1.083
0.75 4.364
4.728 1.083
1.00 3.223 3.596
1.116
1.25
2.001 3.454
1.726
1.50 0.325
4.221 12.986
N=3
-
bo
A
B
B/A
~~
0.25 27.273
27.278
0.50
13.637 13.639
0.75 9.091
9.093
1.00
6.768 6.870
1.25 4.834 6.077
1.50 2.609 6.483
1.75 0.517
7.276
N=4
bo
A B
-
1.0002
1.0002
1.0002
1.015
1.257
2.485
14.061
B/A
0.25 40.914
40.914 1.0000 0.25 54.552
54.552 1.0000
0.50
20.457
20.457 1.OOOO 0.50
27.276 27.276 1.0000
0.75 13.638
13.638 1.0000 0.75 18.184
18.184
1.0000
1.00
10.178
10.279
1.010
1.00
13.586 13.690 1.007
1.25 7.530
8.835 1.173 1.25
10.205 11.616
1.138
1.50
4.629
9.009 1.947
1.50
6.594
11.590 1.758
1.75 1.747
9.942 5.691 1.75 2.928 12.659 4.324
*Based on the Mexican hat function
h(x)
=
2/fi.rr-1/4(1
-
x2)e-xz/2.
The dilation parameter
a.
=
2
in all cases;
N
is the number
of
voices
(see text).
TABLE
V-C
FRAME BOUNDS
FOR
WAVELET FRAMES*
0.125
0.250
0.375
0.500
0.625
0.750
0.875
b0
25.515
26.569
12.758
13.285
8.505
8.856
6.379
6.642
5.101
5.316
3.995 4.686
1.669
5.772
N=3
-
A B
1.041
1.041
1.041
1.041
1.042
1.173
3.459
B/A
0.125
0.250
0.375
0.500
0.625
0.750
0.875
1
.000
bn
39.054
19.527
13.018
9.764
7.808
6.251
3.563
0.163
A
39.073
19.536
13.024
9.768
7.817
6.770
7.598
9.603
N=4
-
B
1.0005
1.0005
1.0005
1.0005
1.001
1.083
2.132
58.929
B/A
~
0.125
0.250
0.375
0.500
0.625
0.750
0.875
1.000
52.085
26.042
17.362
13.022
10.414
8.420
5.313
1.127
52.085
26.042
17.362
13.022
10.420
8.941
9.568
1 1.894
1
.oooo
1
.om0
1
.OoOo
1
.oooo
1.0005
1.062
1.801
10.550
*Based on the
8th
derivative of the Gaussian,
(
2;;;!
)1'2
h(x)=
-
.~-"~(x~-282~ +210x4 -405~' +90)e-XZ/2.
The dilation parameter
a,,
=
2
in
all
cases;
N
is the
number
of
voices.
space lattice in Fig. l(b)) one finds that M(k;2)/m(k;2)
is equal to 3.385. This Feans tha! the ratio
B/A,
which is
bounded below by M(h; 2)/ m(h; 21, is pretty large, with
N
=
1,
even for very small values of
bo.
As
soon as more
voices are introduced, the ratio M/m becomes much
smaller, and snug frames can be constructed, for appro-
priate choices of
bo.
We have restricted ourselves, in
Table Vc, to the choices
N
=
2,3,4, excluding
N
=
1.
iv)
The modulated Gaussian: In this case we take
h(.) =T-1/4(e-lkx-
e-k2/2)e-x2/2
&(
y)
=
T-l/4(
e-(~-k)2/2
-
e-k2/2e-~z/2
)
where
k
=
~(2/ln2)'/*.
Tht subtraction term in the definition of
h,L
ensures
that h(0)
=
0;
for the value of
k
chosen here, this term is
negligible in practice. The value
of
k
has been fixed
so
that the ratio between the highest and the second highest
local maxima
of
Re h is approximately 1/2. This wavelet
is exactly the wavelet used by
J.
Morlet in his numerical
computations [25], [26]. If only real signals
f
are decom-
posed and reconstructed, by means of the (hmn,f), then
the complex wavelet
h
consists really
of
two
wavelets,
Re
h
and Im h. In this case the frame bounds for real
signals can be rewritten
as
with
and
1
p,(
s)
=
-
sup
(k(
atx)
+
€L(
-
a;;.)
1
4xm
.Ik(ab"x
+
s)
+
€k(
-
a;;..
-
s)
1.
Note that
fi
is almost completely concentrated on the
positive frequency kalf line; neglecting terms with nega-
tive arguments for
h
in the previousjormulas leads back
to the frame bounds for support hcR,. In the first
reconstructions with this wavelet, before even the connec-
tion with continuously labelled affine coherent states was
made (see Sections I-E,I-F), a formula similar to (2.1.7)
was used. This reconstruction formula turned out to be
extremely precise. Our calculations of frame bounds show
why. For
N=
4,
bo
=
1, for instance, which are choices
that do correspond to values used in practice (in fact, [251
uses even higher values of
N,
and smaller values
of
bo),
we find
B/A
=
1.0008. Hence
r
=
(B
-
A)/(B
+
A)
=
0.04%, which explains why (2.1.7) is such a good approxi-
mation to the true reconstruction formula.
As
in the previous example, the ratio M/m is rather
large for
N
=
1, and we have computed the frame bounds
only for
N
=
2,3, and 4. They are tabulated in Table V-D.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
988
TABLE
V-D
FRAME
BOUNDS
FOR
WAVELET
FRAMES*
0.5 6.019 7.820
1.299
1
.o
3.009
3.910 1.230
1.5 1.944
2.669 1.373
2.0 1.173
2.287 1.950
2.5 0.486
2.282 4.693
N=3
b
I,
A B B/A
~
0.5
10.295
10.467
1.017
1
.o
5.147 5.234
1.017
1.5 3.366
3.555 1.056
2.0 2.188
3.002 1.372
2.5 1.175
2.977 2.534
3.0 0.320
3.141 9.824
N=4
-
b”
A B B/A
0.5 13.837
13.846 1.0006
1
.o
6.918
6.923 1.0008
1.5 4.540
4.688 1.032
2.0 3.013 3.910
1.297
2.5 1.708
3.829 2.242
3.0 0.597 4.017
6.732
*Based on the modulated Gaussian,
h(x)=T-1/4(e-~kx
-
e-k2/2)e-xz/Z
with
k
=
~(2/ln2)’/~.
The dilation constant
a,,
=
2 in
all
cases; N is the
number
of
voices.
Remark:
The tables show that extremely snug frames
can be obtained for quite reasonable phase space lattices
(i.e.,
N
not too large,
bo
not too small). Note, however,
that even when
B/A
s
not very close to
1,
the frame may
still be useful.
For
B/A
=
1.5,
e.g., the convergence fac-
tor
r
=
(B
-
A)/(B
+
A)
is still of the order of
0.2;
while
this is insufficient to permit the use
of
the approximation
formula
(2.1.71,
it does mean that only a few iterations
will suffice for the computation
of
the
(h,,)“
up to e.g.,
leading, again, to a very accurate reconstruction
formula.
D.
Frames
in
Other Spaces than
L2(R)
The results in this section are more technical and
specialized than those in the preceding sections. The
reader who is mostly interested in ,!,’-results can safely
omit reading this section and go to Section 111, where we
again discuss L2-estimates.
I)
Motivation:
Why
Other Spaces
than
L2(R)?:
So
far,
we have restricted ourselves to studying frames in
L’(R1.
The preceding section was mainly concerned with the
formulation of conditions under which the short-time
Fourier expansions (Weyl-Heisenberg case) or the wavelet
expansions (affine case) would converge with respect to
the L2-norm. As explained in the introduction, both types
of expansions are used in the analysis, e.g., of time-depen-
dent signals. For such signals
f(t>,
the square of the
L2-norm,
j:,dtlf(t)12,
is a natural quantity, often called
IEEE TRANSACTIONS
ON
INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
the “energy”
of
the signal in electrical engineering litera-
ture. It is therefore customary to require L2-convergence
for series representations of these signals.
This does not mean, however, that convergence in
other topologies is not important.
For
example, conver-
gence in
L
P(R)-spaces,
with
p
f
2,
where the coefficients are weighted in a way
different from
L2(R),
would certainly indicate that the
series is more “robust” than
if
it converged in
L2(R)
alone. On the other hand,
if
the signals themselves have
some regularity (consider, e.g., the case where not only
f
but also its first
k
derivatives are
in
L’(R)),
then one
would wish that the partial sums of the series represent-
ing
f
share that regularity, and that the convergence
respects this (in the previous example, this would mean
L2-convergence also for the first
k
derivatives). It would
therefore be interesting to have convergence in the
Sobolev spaces
for at least some
s
>
0.
In the two subsections following this one, we shall show
that for suitably chosen
g
or
h,
and appropriate parame-
ters
p0,p0
or a,,b,, the resulting frames are frames in
&(RI,
at least for some strip
Is1
<
s~,.
In the remainder of
this subsection we give some examples illustrating “what
can go wrong.” The examples given here all pertain to the
wavelet case.
I
want to thank
Y.
Meyer and Ph.
Tchamitchian for having pointed them out to me.
If the
h,,
(h,,(x)
=
a;m/2h(a;mx
-
nb,))
constitute a
frame in
L2(R),
then, as shown in Section 11-A, there
exists a dual frame
{(hm,)-;
rn,
n
E
Z}
such that, for all
f
in
L’W,
f=
C
(hrnn)-(hrnn,f)
(2.4.1)
where the series converges in
L’(R).
If the frame is not
tight, then the
(hm,)-
are not multiples of the
h,,,
and
in general they will not be generated by dilations and
translations of a single function (see Section 11-A).
There are several ways in which
(2.4.1)
may fail
to
extend to
Lp(R),
with
p
#
2,
or to
&(R),
with
s
#
0.
One
possibility is that the coefficients
(h,,,f)
are not well
defined for all
f
in the space under consideration, i.e.,
that
h
does not belong to the dual
of
this space. This is
not really a problem:
it
is enough to impose some regular-
ity and/or decay conditions on
h
to avoid this. Something
much more pernicious may happen, however. It is possi-
ble that even though
h
is a “nice” function, the elements
(/I,,)-
of the dual frame are not,
so
that
(2.4.1)
fails. The
examples we shall give here illustrate this.
The first example is due to
P.-G.
LemariC. It was
communicated to me by
Y.
Meyer. Let
4
be
Y.
Meyer’s
wavelet, as
As
already mentioned, the
$,,(XI
=
m,n
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
989
2-m/2 JI(2-”x
-
n)
constitute an unconditional basis for
many function spaces, including all the
Lp(R),
1
<
p
<
W.
The wavelet coefficients
(JI,,,
f)
can be used to charac-
terize these spaces and their duals [311. In particular,
LP-spaces are characterized as follows: for any function
f
one has the equivalence
ft~p(~)-[
c
2-mI(*mn,f>12Xmn ELP(R)
(2.4.2)
where
xmn
is the indicator function
of
the interval
I,,
=
[2mn, 2”(n
+
1)).
The basic wavelet in Lemarik’s construc-
tion is the following perturbation
of
JI:
h(x)
=
JI(
x)
+
&Tr~1(2x).
This function
h
is clearly in
C”,
and has fast decay at
W.
We use the same dilation and translation parameters as
for
Y.
Meyer’s basis, i.e.,
h,,(x)
=
2-m/2h(2-mx
-
n).
Then
h,,
=
JI,,
-
rJIm-12n
=
(1
-
rU)t+b,,,,, where
U
is the
partial isometry defined by
U+,,
=
JIm-12n.
For
Irl
<
1,
the operator
(1
-
rU) is one-to-one and onto, which means
that the
h,,
still constitute a basis for
L2(W
if Irl
<
1.
The dual frame
(hmn)-
is given by
(hmn)-
=
[(l- rU)(1- r*U*)]
-‘hmn
m,n
Ill2
=
(1-
r*U*)-’+m,
=
r*kU*kJImn (2.4.3)
where
U
*$,
2n
+
=
0,
and
U
*JI,
2n
=
JI,
+
n.
In particular
m
k=O
m
(hOO)A
=
r*k$-kO*
j=O
It turns out that if
Irl>
l/a, this function does not
belong to
Lp(R)
for large
p,
as shown by the following
argument. If we apply (2.4.2) to
(h,)“,
we find
If Irl
>
l/&T,
this shows that
(h,)“
4
Lp(R)
for all
p
>
21n2/[ln2+2ln 11-13. This implies that, even though the
h,,
themselves are
C”
functions with fast decay, and
constitute
a
frame for
L2(R)
(with
A
=(l-
lr12)’/2,
B
=
(1
+
lr12)1/2), the frame expansion (2.4.1) does not extend
to all LP(R)-spaces,
1
<
p
<CO,
if IrI
>
1/a.
Note that, in the example, the
(h,,)“
are the only
functions in the dual frame causing problems. For
n
#
0,
only a finite number
of
terms in the series (2.4.3) con-
tribute, and
(h,,,)-
is still infinitely differentiable and
decaying rapidly. This might lead one to believe that the
problems are caused
by
the fact that the
(h,J
are not
given, in general, by dilations and translations
of
a single
function
h.
It is true, also, that this phenomenon
(h
E
4,
and some
(h,,)”
4
Lp) does not occur for the tight
frames constructed in Section 11-B-2b). For these frames,
results analogous to those for
Y.
Meyer’s basis hold, and
the expansions
f=
A-’
C
hmn(hmn,f)
m,n
are valid, and converge, in particular, for all LP-spaces
(1
<
p
<
w)
and all
<(R).
Nevertheless, there exist (non-
tight) frames for which the
(h,,)“
happen to be dilations
and translations
of
a single functicn
h,
and where, as in
our first example,
h
is “nice” and
h
is not, causing (2.4.1)
to fail in at least some function spaces. Our second
example illustrates this; it is a special case of a construc-
tion made by Ph. Tchamitchian
[353.
In [35], Ph. Tchamitchian constructs functions
u,
r
such
that the dyadic (i.e., ao=2,
bo
=1)
lattices
of
wavelets
generated by
u
and
T
constitute biorthogonal bases for
L~(R),
i.e.,
C
Umn(rmn,
.>
=
(2.4.4)
m,n
where the sum converges strongly in
L2(R>,
and with
The details
of
this construction, together with proofs and
applications, are given in [35b]. It is possible to choose
both
u
and
T
with compact support. One such example is
the following (see [35b]):
U,,(X)=
2-m/2U(2-mX
-
n),
T,,(X)=
2-m/2T(2-mX
-
n).
cos
-
+
-
cos
-
2 16 2 16 2
19
y1
or
1
4
dx)
=
-6
and
0,
Xl-1
l/8,
-1<x<O
-1, O_(x<1/2
1,
1/2<XS1
-1/8, 1~x12
\
0,
x22
where
P(u)
=
3u2
-
2u3. Since P(cos
y)
=
1
+
O(y4),
the
infinite product in the definition of
7^
is well defined. One
finds that
8
is entire and of exponential type, implying
that
T
has compact support. Moreover, since
P(u)
1
u2
on
[O,
11,
m
~~(Y)~SIYI~
c0s4[2-j~/4]
j=
1
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
990
IEEE
TRANSA~IONS
ON
INFORMATION
THEORY, VOL.
36,
NO.
5,
SEPTEMBER
1990
Using this decay
of
i,
the compactness
of
support
7,
and
/&T(x)=
?(O)=
0,
one can easily prove that
~m,fl~(~,~m,,)l
<m.
The decay properties
of
G
are rather
weak, but one can use
/&
a(x)
=
0,
the compactness of
support
U
and the fact that
U
is piecewise constant in an
easy proof
of
Cm,nl(~,~,,)I
<m.
This implies that, for all
sequences
(C,,J,,~
E
in
L2(Z),
m,n
Together with
(2.4.4)
(for the proof of which we refer to
[35b]), this implies that the
U,,
and the
T,,
both consti-
tute frames. Moreover (see
[35]),
both the
U,,,
and the
T,,
constitute bases in
L2(R).
It is now easy to construct the example previously
announced. Take
h(x)
=
7(x).
Then
h
is of compact sup-
port, and
h
belong to
2?5/2-e(R),
for all
E
>
0,
because of
(2.4.5).
Since the
h,,(x)
=
2-m/2h(2-mx
-
n)
constitute a
frame, we can construct the dual frame,
(h,,,)“.
Since the
h,,
are linearly independent, however, and because of
(2.4.4),
we find
(h,,,)“
=
U,,,.
Since
(T
E
&(RI
only
if
s
<
1/2-
E,
we see that
all
the functions in the dual
frame are much less “nice” than those in the original
frame; in particular, they are discontinuous, while
h
itself,
together with its first derivative, is continuous.
2)
Weyl- Heisenberg Frames
in
Sobolev Spaces:
The ex-
amples in the preceding subsection show that one must be
wary when trying to generalize frames, and the associated
expansions, to other function spaces than
L2(R).
One can
however apply the techniques used in Section 11-C to
extend the notion of frame to a “strip” of Sobolev spaces
&,
with
Is1
<
so.
Proposition
2.11:
Define (as in Section 11-C-1)
p,’(
y)
=
sup
(1
+
x’)
Ts’2[
1
+
(x
+
y)’]
+s/2
X
If
c
k#O
then the operator
U,
U=
C
grnn(grnn9
.>
m,n
is bounded, with a bounded inverse, on both
x-,.
In particular, for all
fl
E
&,
f2
E
X,,
and
A,llflll,
I
Il~flllS
I
Bsllfllls
(2.4.7)
A,llf’ll-s
I
Irnf’ll-s
I
~,llf’Il-~
(2.4.8)
where
(
2.4.9)
and
k#O
(2.4.10)
Pro08
We shall show that, for all
f
E
4,
A,llfll,llfll-,
I
(f,Uf)
I
~,llfll,llfll-,.
(2.4.11)
Here, as before, we use the notation
(
,
)
for the duality
extending the L2-inner product,
With respect to
(
,
),
the spaces
&
and
A?-,
are each
other’s dual. On the other hand
U
is symmetric with
respect to
(
,
).
Since
&
is dense in
2?-,,
it follows
therefore from the upper bound in
(2.4.11)
that
U
is
bounded on both
.&
and
A??,,
with norm smaller than
B,.
Similarly the lower bound in
(2.4.11)
implies that, for
all
fl
E
&,
f2
E
S-,,
Il~flIls
2
Asllfllls,
and
lDf2Il-,
2
A,llf21I-,.
Again using the symmetry of
U
with respect to
(
,
)
one easily checks that this implies that
U
is invert-
ible, with a bounded inverse with norm smaller than
A,-’,
both on
&
and
A?-,.
It remains to prove
(2.4.11).
This is done along the
same lines as in Section 11-C.
f(~)*f
x
+
-k
i
:I
2T
40
=
-
/&
[
(1
+
xy21
f(
x)
I]
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
99
1
DAUBECHIES: THE WAVELET
TRANSFORM,
TIME-FREQUENCY
LOCALIZATION
AND SIGNAL
ANALYSIS
with
The bounds (2.4.11) then follow immediately.
I3
Remarks:
1) If the conditions of Proposition 2.11 are satisfied,
then, since
U
is invertible, and has bounded inverse
on
&,
we have
6mn
=U-’gmn
E
&
and, for all
f
E
3,
f=
C
irnn(gmn,f)
m,n
where the series converges in
&:
the frame expan-
sion holds on
&.
2) If
U
is a bounded and invertible operator on both
&
and
A?,,
then, by standard (highly nontrivial)
interpolation theorems (see e.g., Section IX-4 in
[64]), it is automatically bounded and invertible on
any
&,
with
ls‘l
is.
Proposition 2.11 gives thus a
sufficient condition for the frame expansion formula
to hold on a “strip” of Sobolev spaces. To obtain a
wide “strip,” for fixed
po,
it is clear from (2.4.6) that
we have to choose
qo
sufficiently small. Typically,
we would expect the critical value
q,C(s)
(the value of
qo
for which equality occurs in (2.4.6)) to be a
decreasing function of
s.
Note that one needs to
impose a decay condition on
p’(s>,
similar to
(2.3.131, to ensure the existence of
q,C(s).
3) Since
C,
E
,12(x
+
mpJI
IB(x
+
mp,
+
y)l is periodic
in
x,
with period
p,,
and since [1+(x
+
y)’]/
(1+x2)
has its maximum, resp. minimum, at
x=
-
y
/2
sgn (y)dw, it suffices, for numerical
computation of
P”(y),
to take the supremum over
values of
x
in an interval of length
po
around
-
y/2+sgn(y)\/l+y2/4.
Example:
For
g(x)=
r-‘l4
exp(- x2/2), Table VI-A
gives the values of
A,
and
B,
for a few values of
s,
for
po
=
r/2,
qo
=
1. Table VI-B shows how
q,C(s)
changes
with
s,
for fixed
po
=
r/2.
TABLE VI-A
FRAME BOUNDS*
S
A,
B, B,
/A,
0.0
3.853
4.147 1.076
1.0 3.852 4.148 1.077
2.0 3.849
4.151 1.079
3.0 3.836
4.164 1.086
4.0 3.787 4.213 1.112
5.0
3.600 4.400 1.222
6.0 2.865
5.135 1.793
*In the Sobolev spaces
for Weyl-Heis-
enberg frames based on the Gaussian
g(x)=
~r’/~
exp(-
x2/2),
with
p,,
=
~/2,
9,,
=
1.0,
for
changing values
of
s.
For
s
=
7,
our estimate for
A,
becomes negative: the frame breaks down.
TABLE VI-B*
0.0
3.99
1
.o
2.28
2.0 1.72
3.0 1.42
4.0 1.24
5.0 1.13
6.0 1.06
7.0 0.99
*The critical value
4$s)
for the
translation parameter
qo,
as
a
function
of
the index
s
of the
Sobolev space
in
which the frame is
consdered. Values of
qo
smaller
than
q$s)
lead
to
a frame in
4
and
Z,.
The basic function here
is g(x)=Tr’/4exp(-x2/2);
po=
rr/2
is fixed.
3)
Wavelet Frames in Sobolev Spaces:
Since the tech-
niques used for proving frame bounds in
L2(R)
were
essentially the same for the wavelet case as for the
Weyl-Heisenberg case, it is not surprising that we can
prove the following proposition.
Proposition
2.12:
Define (as in Theorem
2.7)
m(h;a,)
=
inf
~A(n;x)
12,
M(
h;
a,)
=
sup
I
i(
ay.)
12.
mcZ
X
m6L
Assume that
m(h;
a,)
>
0,
M(h;
a,)
<
m.
Define, for
s
2
0,
P’(
y)
=
sup (1
+
x’)
Ts/2
I
&(
a;;.)
I
(&I
ayx
+
y)
I
X
mtL
If
c
[
p:
(2k)p;
(-
Z-k)]’”
<
m(h;a,)
(2.4.12)
k+O
then the operator
U,
is bounded, with a bounded inverse, on both
&
and
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
992
IEEE TRANSACTIONS
ON
INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
Z-,.
In particular, for all
fl
E
e,
f2
E
2-,,
TABLE
VI1
FRAME
BOUNDS*
A,llflll,
IDflIlS
I
B,llfills
(2.4.13)
b,,
=
1.0
b,,
=
1.25
s
A, B, B,/A,
s
A, B,
4/A,
Asllf211-,
I
lDJf2ll-s
I
~,llf2ll-s
(2.4.14)
0.00 3.223 3.596 1.116
0.00
2.001 3.454 1726
where
0.25 3.223 3.596 1.116 0.25 1.995 3.460 1.734
0.50 3.222 3.597 1.116 0.50 1.985 3.470 1.748
0.75 3.221 3.597 1.117 0.75 1.971 3.484 1.768
1.00 3.220 3.599 1.118 1.00 1.953 3.502 1.793
m(h;a,)-
P:
-k
p,-
--k
1.25 1.926 3.529 1.832
1.50 3.216 3.602 1.120
1.50
1.877 3.578 1.906
1.25 3.218 3.600 1.119
1.75 3.214 3.605 1.122 1.75 1.794 3.661 2.041
k#O
[
(
)
(
2
)]‘I2]
kzO
[
(
’bi:
)
(
’bi:
)I
”4
In
the Sobolev spaces
<
for
wavelet frames based on
the
M(h;a,)-
P:
-k
p,-
--k
.
Mexican hat function
h(x)
=
23-‘/’~-’/~(1-
x’)exp(-
x2/2),
Po
with
a,
=
2.0,
b,,
=
1.0
and
1.25
for
changing values
of
s.
Proofi
The proof is entirely analogous to the proof of
Example:
Table VI1 gives
A,
and
B,,
for a few values
of
s,
for the Mexican hat function
h(x)
=
2/fi~-‘/~(l-
Proposition
2.11.
I.
Remarks:
~~)e’-~’/~,
for
a,
=
2.0,
and for
b,
=
1.0
and
1.25.
If
U
is bounded, with a bounded inverse,
on
e,
then
(h,,)“
=T-’h,,
E
f
=
C
(hmn)“(hmn,f)
(2.4.15)
and, for all
f
E
e,
m,n
where the series converges in
&.
This means that
the phenomenon illustrated by the examples in Sec-
tion 11-D-1 cannot happen, at least in
&,
if
h
satisfies the conditions in Proposition
2.12.
By interpolation (see e.g., Section IX-4 in
[64]),
one
finds that if
(2.4.13), (2.4.14)
hold in
&,
2-,,
respectively, then
U
is bounded, with a bounded
inverse, on all
&,
with
Is’I
I
s.
Under the condi-
tions in Proposition
2.12,
the frame expansion
(2.4.15)
is therefore valid in all
&,
with
Is’I
I
s.
Typically (as in the Weyl-Heisenberg case), we ex-
pect that, for fixed
a,,
the critical value
bG(s)
(i.e.,
the value of
b,
for which equality holds in
(2.4.12))
decreases with
s.
It is a remarkable fact that for
Y.
Meyer’s basis, the wavelet expansion is valid in
e,
for all
s
E
R,
for
a,
=
2,
and for
Jijred
bo
=
1.
Some-
thing similar is true for the tight frames constructed
in Section
11-B-2b).
However, for general functions
h,
leading to nontight frames, we rather expect
b$s)
to decrease with
s.
For
a given function
h,
the strip of Sobolev spaces
for which the
h,,
constitute a frame, i.e., the possi-
ble values of
s
for which
(2.4.131, (2.4.14)
holds, is
!onstrained by the behavior of
6
around zero. If
h(x)
=
O(xO)
for
x
+
0,
then clearly (see the defini-
tion
of
p:)
(y)
2
C[
inf
~i;(y
+
u>lly
+
This diverges for
s
2
cy.
am(a-s)
Id
5
arM
m
=
--?o
111. PHASE
SPACE
LOCALtZATION
Let us recall the intuition, already mentioned in the
introduction, which leads us to expect the phase space
localization results we shall give here.
Both the Weyl-Heisenberg coherent states and the
wavelets can be used to give a representation in the
time-frequency plane of time-dependent signals, provided
the basic functions
g
or
h
and the parameters
po,q,
or
a,,b,
are suitably chosen (see Section 11). A graphical
picture
of
these representations is given in Fig.
1.
Ideally,
one would like these representations to be reasonably
“sharp.” If e.g., the pair
(mo,
no)
corresponds to the time
t,
and the frequency
w,
(see Fig.
11,
then we would wish
that the frequency content, in a band around
wo,
of the
signal
f,
during a time interval around
to,
is essentially
mirrored by the coefficients
(g,,,f)
or
(h,,,f)
with
m
close to
mo,
n
close to
no.
It is intuitively clear that the
basic analyzing functions
g
or
h
have to be themselves
well localized in time and frequency for such “sharpness”
of the associated representations to be attainable.
In this section we shall try to make these qualitative
statements more precise. We shall do this by giving a
sense to the “sharpness”
of
the time-frequency represen-
tation, and by showing how the localization, in time and
frequency,
of
the analyzing functions
g
or
h
matters. The
Weyl-Heisenberg case shall be discussed in Section 111-A,
the wavelet case in Section 111-B. In both cases we shall
see that signals that are essentially limited to a given
finite time interval and to a given finite range in fre-
quency can essentially be represented by a finite number
of expansion coefficients. (All these qualifications will be
made more quantitative next). We shall use this fact to
explain, in Section 111-C, a phenomenon that was first
noticed by
J.
Morlet in numerical calculations. To recon-
struct
a
signal
f
with a precision
E,
it is sufficient, for
some frames,
to
calculate the expansion coefficients with
a precision
CE,
where
C
turns out to be significantly
larger than would be expected for orthonormal bases. We
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL. ANALYSIS
993
have called this phenomenon the “reduction of calcula-
tional noise” (for example, it often reduces round-off
errors), and we explain it in Section
111-C.
A.
The
Weyl-
Heisenberg Case
Assume that
g
is normalized,
/’&
Ig(x)12
=
1, and that
l~xlg(x)12=o=ldYYlg^(Y)12.
Then
g,,
is localized around the phase space point
hp,,nq,),
/&xlg,,(x)
I2
=
nq,,
/dyy((g,,)^
(Y)
l2
=
mp,.
Suppose, on the other hand, that we restrict ourselves
to the analysis and reconstruction of signals that are
essentially time-limited to the interval
[
-
T, TI
and essen-
tially band-limited (limited in frequency) to the interval
[
-
R,
RI.
We have introduced the word “essentially” in
this statement because, as is well-known, no function
f
can have both a compact support and a Fourier transform
with compact support. A more precise statement of the
“essential” time- and band-limitedness is
11(1-
QT>fII
<<
llfll
11(1-
Pn)fll
<<
llfll
(
QT~)
(1)
=
X[
-
~,~I(t)f(t)
where
VnfY
(w)
=
X[-n,n](w)f(w)
and where
x,
denotes the indicator function of the inter-
val
I.
Effectively, these limitations single out a rectangle
of phase space as more important than other regions.
We shall assume, in what follows, that the
g,,
consti-
tute a frame, with frame bounds
A
and
B
and with dual
frame
g,,.
The reconstruction formula, valid for all func-
tions in
L2(R),
and therefore in particular for the func-
tions
f
of interest here, is (see Section 11-A)
f=
C
irnn(grnn,f).
(3.1)
m,n
E
Z
If the
g,,
are “well localized” in phase space around
(mp,,nq,),
then it is to be expected that
(g,,,f)
will be
small if the distance, in phase space, from
(mp,,nq,)
to
the rectangle
[
-
R,
R]
x
[
-
T,
TI,
is large. In other words,
one expects that only those
m,
n
for which
(mpo,
nq,)
lies
in or close to
[
-
R,R]X[-
T,T]
will play a significant
role in the reconstruction (3.1)
of
f.
Fig.
6
represents the
situation.
As
in Fig. l(a), the
g,,
are represented by their
“phase space centers”
(mp,,
nq,).
The signal
f
is essentially concentrated, in phase space,
on the rectangle
[
-
R,
RI
X
[
-
T, TI.
Under suitable con-
ditions on
g,
it turns out that, for all
E
>
0,
there exist
t,,
w,
such that the partial reconstruction
of
f
using only
the (finitely many)
m,n
associated to the “enlarged rect-
angle”
[-(a
+
w,),(R
+
w,)lx[-(T
+
t,),(T
+
t,)l
(in
.
.
.
.
.
.
.
.
-
.
.
.
.
.
-k
I.
I.
I.
I.
1.
I
t”
.
.
.
.
.
.
.
-c
.
.
.
.
+
t
*i
:
....
L-*-Z-*-Z--Z-*-Z-*-3
a.....
.
1
. . . . . .
Fig.
6.
Rectangular lattice
(nqo, mp,)
indicating localization
of
gmnr
and rectangle in phase space
[
-
T,
TI
X
[
-
0,
a]
on which signal
f
is
mainly concentrated. Coefficients
(g,,,
f)
corresponding
to
(nq,,
mpo)
in enlarged rectangle (in dashed lines) suffice to recon-
struct
f
up to error
of
order
E.
dashed lines in the figure), is equal to
f,
up to an error
of
order
E.
This is essentially the content
of
the following
theorem.
Theorem
3.1:
Suppose that the
g,,(x>
=
eimPoxg(x
-
nq,)
constitute a frame, with frame bounds
A,
B.
Assume
that
I
g(
x)
1
I
C(
1
+
x2)
-a,
1
g(
y)
1
I
c(1+
y2>-
for some
C
<w,
a
>
1/2. Then, for any
E
>
0,
there exist
t,,
w,
>
0
such that, for all
f
E
L2(R),
and for all
T,
R
>
0,
+
\I(
1
-
QT)fI(
+
ellfll]
(3.2)
Proof
See Appendix
D.
0
where the
g,,
constitute the dual frame to the
g,,.
Remarks:
1)
In the limit as
E
+
0,
one finds
t,
+w
or
w,
+W.
(With our proof, in Appendix
D,
both
t,
and
w,
tend to
03
as
E
+
0.
If
g
or
g
has compact support,
then
t,
or
w,
can be kept finite. In all cases at least
one
of
t,,
w,
must diverge as
E
+
0.)
This is natural;
infinite precision cannot be obtained when using
only a finite set of
g,,.
In particular, for
g(x)=
~-‘/~exp(- x2/2),onefinds
w,,t,
-E+OCllog~l’’2.
2) Note that the decay conditions on
g
and
2
exclude
all orthonormal bases
g,,,
by Theorem 2.3.
3) The important fact about Theorem 3.1 is that
c,,w,
are
independent
of
T,
R:
the “enlargement proce-
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
994
IEEE TRANSACTIONS ON INFORMATION THEORY,
VOL.
36,
NO.
5, SEPTEMBER 1990
dure” depends only on
E,
the desired precision of
the finite construction. For fixed
E,
the number of
points
N,(T,R)
used in this finite reconstruction is
4(T
+
t,XR
+
w,)/p,.q,.
Hence
lim (4TR)-’N,(T,R)
=(po.qo)-’,
(3.3)
T,R
--lm
which is independent of
E.
This can be compared
with an analogous result involving prolate spheroidal
wave functions (see [65], [66]; the formula discussed
here is explained very clearly in [66]). The prolate
spheroidal wave functions are the eigenfunctions of
the compact operator
PnQTPn
(which also de-
scribes localization in phase space, singling out the
rectangle
[
-
R,
RI
X
[
-
T, TI). Signals
f
that are
essentially time-limited to
[
-
T, TI and bandlimited
to
[
-
R,
R]
can be expanded in prolate spheroidal
wave functions. Again, if a reconstruction up to a
finite error
E
is
desired, one can truncate the expan-
sion to a finite sum. The number,
rt,(T,
R),
of
terms
needed is the number of eigenfunctions of
PnQ,Pn
with eigenvalue larger than
E.
One has [651, [661,
2TR
n,(T,R)
=
-
+
CElog(TR)
+
o(E).
7r
In this case
This limit is exactly the Nyquist density. In fact, this
result was the first rigorous formulation of the intuitive
Nyquist density idea [65]. If we compare (3.3) with (3.41,
then we see that in our present approach, the density
(po.qq)-l
is higher than the Nyquist density (2.srI-l. We
know indeed (see Section 11-C-la)) that
po.qo
_<
27r for
all frames
{g,,;
m,n
E
h}.
For the examples with good
phase space localization (measured by e.g., higher mo-
ments of
Jgl
and
lgl),
we even have, by Theorem 2.3, that
po*qo
<
27r.
The “oversampling” of our phase space den-
sity with respect to the optimal Nyquist density, measured
by the ratio 27r(pO.qJ1
>
1, is the price we have to pay
for the fact that the frames of interest to us
are, in
general, not orthonormal. We also gain something with
respect to the prolate spheroidal wave functions, however.
The construction of the different
g,,,
obtained from one
function
g
by translations in phase space, is simpler than
the Construction of the (orthonormal) prolate spheroidal
wave functions.
Note that (3.3) can in fact be considered as a definition
of the phase space density for the frame under considera-
tion. While we have used the term “phase space density”
before in heuristic discussions, (3.3) is the first mathemat-
ically precise statement justifying this terminology.
Example: In the Table
VI11
we give the values of
f,
=
w,
corresponding to given
E
for
g(x)
=
7r-’l4
exp(
-
x2/2),
in the cases
p,=q,=~’/~
and po=q,,=(7r/2)1/2. In
each case we have used (D.6) in the estimates.
TABLE
VI11
THE
“ENLARGEMENT
PARAMETER”
I,*
pII
=
ql,
=
=
1.25
E
t,
=
w,
0.1
0.05
0.01
2.52
2.78
3.31
0.005 3.51
0.001 3.94
0.0005 4.11
0.0001 4.48
p,l=90=~=1.77
E
1.
=
w,
0.1 2.55
0.05
2.81
0.01 3.33
0.005 3.54
0.001 3.97
0.0005 4.14
0.0001 4.50
*As
function
of
the error
E,
for
the
Weyl-Heisenberg frame
of
Gaussians,
respectively
for
po
=
90
=
m,
po
=
9”
=
J;;
(see text)
B.
The Wavelet Case
In this case we assume that
h
is normalized
so
that
jdr lh(x)I2
=
1,
and that
j’dxxlhJx)12
=
0.
Let us assupe,
for the sake of simplicity, that
Jhl
is even (in practice,
h
is
either even or odd; even if the frame
is
constructed by
means of a function
h
with support
h
c
R,,
then the
effective basic wnavelets
h’
=
Re
h, h2
=
Im
h
satisfy the
condition that
Ih’l
is even-see the remarks following
Theorem
2.7
and 2.8). Let us also assume that
(this does not imply any
loss
of generality: it can easily be
achieved by dilating
h).
Then
h,,
is concentrated around
the phase space points
(
t-
a;,,
arnb,)
Lrndkkl(
h,,)”
(k)
l2
=
akm
=
-
Io
dkkl(
hm,j
(k)
1’.
-m
Again, we suppose we are mainly interested in func-
tions
f
localized in phase space. In this case, we assume
that they are essentially time-limited to
[
-
T,
TI, and with
frequencies
IwI
mainly concentrated in
[a,,
a,], where
0
<
R,
<
R,
<
w.
The need for a lower bound
a,
on the
frequencies
Iw
I,
as opposed to the Weyl-Heisenberg case,
where we only introduced an upper bound, stems from
the logarithmic rather than linear treatment of frequen-
cies by
the
wavelet transform.
Fig.
7
represents the situation graphically. The dots
represent the “phase space localization centers” of the
hm,;
for the sake of simplicity we have taken
a,,
=
2. The
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES:
THE
WAVELET
TRANSFORM,
TIME-FREQUENCY
LOCALIZATION
AND
SIGNAL ANALYSIS
995
7
................................................
I
r-----T-----
I
+t
I
L-----
-----I
I
................................................
t
Fig.
7.
Lattice
Moa;,
k
aGrnk,),
indicating localization of
h,,
(see
Fig.
l(b)),
and
two
rectangles
[-T,T]X[R,,R,], [-T,T]x[-R,,
-
R,]
on
which signal
f
is mainly concentrated. Coefficients
(h,,,f)
corresponding
to
lattice points within set
B,
(in dashed lines) suffice
to
reconstruct
f
up to error
E.
signals
f
of interest are essentially concentrated in the set
[-
T,TlX([(-
RI,
-
R,]U[R,,R,]), marked with full
lines in the figure.
We shall assume, of course, that the
h,,
constitute a
frame, with frame bounds
A,
B
and with dual frame
(h,,J.
The associated reconstruction formula is then
This formula is valid for all functions in
L2(R).
For signals
essentially concentrated in
[
-
T, TI
X
([
-
RI,
-
R,]
U
[a,,
RI]) we can again restrict ourselves to a finite subset
B,(T,R,,R,)
of indexes, provided the basic wavelet
h
is
itself sufficiently concentrated. Partial reconstruction of
such a signal
f,
using only the pairs
(m,
n)
E
B,,
is then
an approximation of
f
with an error at most equal to
E.
The set
B,
includes all the
(m,n)
for which
R,
I
aim
I
RI,
and
Ja,“nb,l
I
T; it is indicated in dashed lines in Fig.
7.
The following theorem gives an exact statement of this
result.
Theorem
3.2:
Suppose that the
hmn(
X)
=
airnI2h(
aimx
-
nb,)
constitute a frame, with frame bounds
A,B,
and dual
frame
(h,,)“.
Assume that
where
p
>
0,
a
>
1, and that, for some
y
>
1/2
/&(
1
+
x2)’1
h(
x)
1’
<w.
Fix T
>
0, 0
<
R,,
<
RI.
Then, for any
E
>
0,
there exists a
finite subset
B,(T,R,,R,)
of
Z2
such that, for all
f
E
L2(R),
(3.6)
Proof
See Appendix D.
0
Remarks:
1) The “enlargement procedure,” i.e., the transition
from the original “box”
[-
T,TIx([-
RI,
-
R,]u
[R,,R,])
to B,(T,R,,R,), is more complicated here
than in the Weyl-Heisenberg case; the parameters
m,, m,,
and
t
also depend on
R,,R,
and not only
on
E
(see the proof in Appendix D).
2) The construction of the set
B,
(see also Fig. 7)
exhibits the fact that wavelets give a higher resolu-
tion at high frequencies than at low frequencies. For
fixed
m,
the “extension” of the box in the time-vari-
able, as defined by (D.7), corresponds to considera-
tion of all the pairs
(m,
n)
with time-localization
la,”nb,l
I
T
+
art.
The “extension”
art
thus de-
pends on
m
and is small for large negative values of
m,
which correspond to high frequencies.
3) A crude estimate leads to
#Be(
T,
a,
9
1
)
If
R,
+
0,
T, and
RI
+CO,
then
CE-
I/P
2bo In
a,
(4TR,)-’[#B,(T,R,,Rl)]
f
~
(3.8)
which is not independent of E. While the estimate
(3.7) is admittedly crude, finer estimates lead to a
similar result. This is in contrast with the analogous
result for the Weyl-Heisenberg case (see (3.3))
where the corresponding limit was independent of
E,
and gave the phase space density of the frame.
In
fact, it gave a procedure to
define
the phase space
density of the frame. Because
of
the €-dependence
of the right-hand side of (3.7), we cannot use the
same procedure to define a phase space density
corresponding to wavelet frames. This
illustrates
again (see also the discussion in Section II-C-2a))
that the concept “phase space density” is not well-
suited to the wavelet representation.
4) The estimates made in the proof
of
Theorem 3.2
lead to rather crude bounds. As in the Weyl-Hei-
senberg case, it is possible to write more compli-
cated, but less coarse estimates. For the choice
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
996
IEEE
TRANSACXONS ON
INFORMATION
THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
h(x)
=
2.3-1’2~-’/4(1
-
x2)e-x2/2,
a,
=
2.0,
b,
=
0.5,
with
fl,
=
10,
fl,
=
1000,
and
T
=
100,
one finds
E
mil
ml
t
0.1
-
11
-2
4.95
0.05
-
12
-2 4.97
0.01
-
13
-2 5.75.
C.
The
Reduction
of
Calculational
Noise
J.
Morlet noticed, some time ago, that in numerical
wavelet calculations, it often sufficed to calculate the
wavelet coefficients to a precision of, say, to be able
to reconstruct the original signal with a precision of, say,
This rather surprising fact can be explained as a
consequence of both phase space localization, and “over-
sampling.”
Phase space localization is necessary to restrict oneself
to a finite number
of
coefficients. We cannot hope to
control an infinite number of coefficients if they can all
induce an error of the same order. The role
of
“oversam-
pling” is the following. Let us go back to the frame
operator
T
(not to be confused with the time-limit
T
in
Sections 111-A and 111-B) defined in Sections I-C and
11-A. We have
T:
L2(R)
+
12(E2)
(Tf)m,n
=
(4rnn9f)
where
+,,,
stands for either
h,,
or
g,,.
Since the
4m,
constitute a frame, this operator is bounded and has a
bounded inverse on its closed range. The operator
T
is
onto (its range is all of
12(Z2))
if and only
if
the
$,,,
constitute a basis. In general, however, the
4,,,
are not
independent, and the range
of
T (RanT)
is a proper
subspace
of
12(Z
2).
The inversion procedure,
f=
C
(4rnn)-(4rnn?f)
m,n
when applied to elements
c
of
12(Z2)
not necessarily in
Ran
T:
C
(4mn)“Cmn
m,n
in fact consists
of
1)
a projection of
12(Z2)
onto
RanT,
2)
the inversion of
T
on its range (see Section 11-A). We
shall model the finite precision
of
numerical calculations
by adding random “noise” to the coefficients
(4,,,
f),
thus leading to modified coefficients
c,,,(f).
The “noise”
component of these coefficients “lives” on all of
12(Z2).
If
we apply the inversion procedure, this component will
therefore be reduced in norm by the projection onto
RanT.
This reduction will be the more pronounced the
“smaller”
RanT
is, as a subspace
of
12(Z2),
i.e., the more
pronounced the oversampling of redundancy in the frame.
The calculations below show how this work in practice.
Let us assume that we are interested in signals
f
that
are essentially localised in the time interval
[
-
T, TI,
and
in the frequency range
[
-
R,
fl]
(in the Weyl-Heisenberg
case) or
[-
RI,
-
fl,,]U[fl,,,fl,]
(in the wavelet case), i.e.,
I\(
1
-
Q~)fl(
I
~llfll
II(
n
-
~,)fll
I
~Ilfll
or
II(
n
-
pn,
+
p,,,)fI(
I
EII~II.
Then, by Theorems
3.1
and
3.2,
there exists an “enlarged
box”
B,
such that
llf-
c
(4rno)-<+rnn,f>
11
5
3(~/~)1/~Ellfll
(m,n)E
E,
where
4
denotes either
g
or
h.
Since
B,
is a finite subset
of
E’,
we restrict ourselves therefore to the finitely many
coefficients
(+,,,
f).
In practical calculations, the coefficients
(4,,,
f
)
will
be computed with finite precision. Let us take the follow-
ing model for the errors. Assume that the coefficients to
be used in the calculations are given by
cmn(f)
=
(4mn,f)
+
ymn
where the
ymn
are independent identically distributed
random variables, with mean zero, and with variance
a2,
E(y&J
=
a’.
This means that the
(4,,,f)
are known with “precision”
a.
Note that our model is only a first approximation. In
general the
$I,,,,
and hence the
(+,,,f),
are not linearly
independent, which means that the round-off errors
should not be regarded as independent random variables.
With this approximation, we find that the estimated error
between
f
and a partial reconstruction, using only the
finitely many coefficients associated to
(m,
n)
E
B,,
and
even those only with finite precision (i.e., replace
(4,,,
f
)
by
c,,,(fN,
is
given by
=
#-
(,,,)E
c
E,
(4rnn)-(4rnn,f))
-
c
ymn(
4rnn)-
(m,n)EB,
I
9( B/A)~~llfIl~
+
A-2a2N,
(3.9)
where
N,
=
#Be,
and where we have used
E(y,,)
=
0,
E(-yrnnym.,.)
=
t3mm,8nnfa2,
and
Il(4,,)-
112
=
~~~-14mn~~2
I
A-2114mn112
=
A-2
(with
U
as defined in Section 11-A).
The “reduction of calculational noise,” observed by
J.
Morlet, is contained in the second term in
(3.91,
more
particular in the factor
N,A-*.
Let us show how.
Assume that we are considering a snug Weyl-Heisen-
berg frame,
gm,.
If we assume that
B,
is large with
respect to the lattice mesh, then (see Section 111-A)
4Tfl
Po
9,
N,
=
#B,
-.
On the other hand,
if
the frame is snug (i.e.,
B
=
A),
we
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM. TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
997
find, by (2.2.9),
A-27r(p0.q,)-’
(we assume
llgll=
1). Hence
N,A-Z=
7r-2TR(po.q0).
(3.10)
If the
g,,
had constituted an orthonormal basis, then
(provided we neglect the
loss
in phase space localisation
due to the use of an orthonormal basis) this factor would
have been
(NcA-2)orthon.basis
(T).
(3.11)
The frame gives thus
a net gain
of
27r/po.q0 with
respect to the orthonormal basis situation.
Something similar happens for wavelets. In this case we
don’t have such a simple expression for
NE,
but we can
easily see that the same phenomenon takes place by the
following argument. Suppose
h,
U,,
b, are chosen
so
that
the frame is snug (i.e., it is tight for all practical purposes).
In particular this means that
m(h;
a,)
=
M(h;
U,)
while
the p-terms in (2.3.231, (2.3.24) are negligible. Conse-
quently
A
=
B
2:
27rb;’m(h;
U,).
Consider now the frame
with the same
h,u,,
but with bh
=
b,/2. This frame will
obviously also be snug, with
A’
=
B‘
2:
27rbh-’m(h;
a,)
=
2A. On the other hand, there are twice as many points in
the graphical representation of this new frame, for every
frequency level. Hence
N,‘
=
2Nf. Combining these two,
we find
N,‘AfW2
=
iN,A-2,
i.e., halving
b,
leads to a gain
of 2 in the total error
on
f,
for the same precision
on
the
coefficients.
For the frames used by
J.
Morlet when he noticed this
phenomenon, which were heavily oversampled (e.g., he
used up to
15
“voices”-see the end of Section 11-C-2a
for a definition), a gain factor of
10
or more can be
obtained easily. Note, however, that oversampling does
not explain completely the observed calculational noise
(or quantization noise) reduction.
As
in vision analysis
[38] part of the reduction is a consequence of the fact
that, unlike the original signal, the coefficients
cm,(f>
at
every fixed m-level are distributed around zero, with a
sharp peak at zero. This makes it possible to drastically
reduce the number
of
quantization steps in the
cmn,
without significantly altering the quality of the recon-
structed signal [381.
2TR
IV. CONCLUSION
We have shown how to characterize functions
f
by
means of a local time-frequency analysis, by computing
their inner products with either Weyl-Heisenberg coher-
ent states,
or with wavelets,
c,,(
f)
=
~,~/’/dXf(
x)h(
ugmx
-
nb,,)
The first approach corresponds to the windowed Fourier
transform, the second is the wavelet transform. The
wavelet transform handles frequencies in a logarithmic
rather than linear way, and seems better adapted to the
analysis of acoustic and visual signals than the windowed
Fourier transform.
In both cases we have formulated necessary and suffi-
cient conditions for the stable reconstruction
of
f
from
the
c,,<f).
For such a stable reconstruction algorithm to
exist, we require that, for some
A
>
0,
B
<m,
and all
Allfll’
I
Ic,,(f)
1’
I
Bllfl12.
(4.1)
We have provided a reconstruction algorithm, which con-
verges at least as fast as a geometric series in
r
=
B/A
-
1,
and we have presented efficient methods for estimating
A
and
B.
These methods are illustrated by many exam-
ples.
Finally, if
g
respectively,
h
is well localized in both
time and frequency, and
if
(4.1) is satisfied, we have
shown that the characterization of functions
f
by their
coefficients
cm,(f)
is truly local in time-frequency. If
f
is
essentially concentrated
on
a limited region in time-
frequency, then only the
cm,(f)
corresponding to time-
frequency points within or close to this region are needed
for an approximate reconstruction of
f.
f
E
L2(W
m,neZ
ACKNOWLEDGMENT
It is a pleasure for me to thank the many people with
whom
I
have had enjoyable discussions
on
the subject of
this paper, who pointed out relevant references, and who
raised interesting questions. First of all, I want to express
my gratitude to
A.
Grossmann, who introduced me to the
many properties of coherent states years ago, and more
recently stimulated my interest in “frame problems.” This
paper would not have existed without his continued inter-
est and encouragement. It has been a pleasure to discuss
the topics in this paper with him.
The completed proof of the Balian theorem, in Section
11-C-la), is due to
R.
Coifman and
S.
Semmes. I want to
thank them for letting me include it here. Thanks are also
due to
R.
Howe and
T.
Steger for solving one of my
conjectures and for drawing my attention to reference
[49]. The refinements of the frame bounds in Section
11-C-2a) are due to Ph. Tchamitchian. Section 11-D,
on
frame bounds and convergence in other spaces than
L2(R),
would not have existed without
Y.
Meyer and Ph.
Tchamitchian, who pointed out the problem to me, and
who suggested that a modification of the L2-estimates
would lead to useful Sobolev-space estimates.
I
would also like to thank P. Deift, H. Feichtinger, P.
Jones,
H.
Landau, P. Lax,
R.
Littlejohn, M. Sirugue, and
D. Thomson for many interesting discussions on one or
several subjects of this paper.
I
am also grateful to
C.
Tomei and to J.
R.
Klauder, who suggested the terminol-
ogy
“tight frame” and “snug frame,” respectively.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
998
IEEE
TRANSACTIONS
ON INFORMATION THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
Finally,
I
would like to thank the referees for making
many
suggestions that improved the readability of this
paper.
APPENDIX A
RESOLUTIONS
OF
THE
IDENTITY
By explicit computation we have
1
da
=
-
/
/db
/dyfi(
x
)
*
I
a
I
fi
(a)
fi
(
ay)
-y’f2(
y
)
2T
a
APPENDIX
B
PROOF
OF
LEMMA
2.4
We assume that
IG(t,
s)
I
I
b
<m
(B.1)
and that
G,
d,G
and
a,G
are locally square integrable. We show
that, together with the “periodicity conditions”
G(t
+l,s)
=G(t,s)
G(t,
s
+
1)
=
e2Ti‘G(
t,
s)
(B.2)
the extra assumption
JG(t,s)l?a>O
(B.3)
necessarily leads to a contradiction. To do this we introduce an
averaged version
Gr
of
G.
More precisely, define, for r
>
0,
Then
G,
is obviously continuous. For
It
-
t’l
<
r,
Is
-
s’I
<
r one
has
I
Gr(
t
,
s)
-
Gr(
t’,
s’)
I
I
br-
(
It
-
t’/
+
IS
-
s’l)
.
(B.4)
(B.21, but instead a modified version of them:
G,(t+l,s)=G,(t,s)
1
Gr
(
t
,
s
+
1
)
=
-
/
dt’
i
eZT“’G(
t’,
s’)
4r2
1t’-
11
<
r
s’-
SI
<
r
=
e
TirGr
(
t
,
s
)
+
+
(
t
,
s
)
03.5)
I+(~,s)II
2rbr. (B.6)
where
By choosing r small enough, we can make the deviation of (B.5)
from (B.2), as small as desired. The only other ingredient
needed
is
a set of bounds (upper and lower) on
lGrl.
The upper
bound is immediate from (B.l),
IG,(t,s)li
b.
For the lower bound we restrict ourselves to a neighborhood
U
of
[0,
212. Choose r such that, for all
(t,
s)
E
U,
The function
Gr
does not satisfy the “periodicity” conditions
,
,\
I
/I
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
999
If we choose
a
=
a/8b,
E
=
aa/8
=
a2/64b,
then the right
hand side of
(B.10)
reduces to
a/2,
and we conclude
a/21IG,(t,s)ls b. (B.ll)
We have now all the necessary ingredients. Since
G,
is contin-
uous, and satisfies
(B.11)
on
U,
with
a
>
0,
b
<m,
y,
=
log
G,
can
be defined as a continuous, univalued function on
U.
As
a
consequence of
(B.5)
we see that, for all
(t,s)~
V=
U
n
(U
-(l,O))n(U
-(O,
l)),
yr(
t
+
1,
s)
=
y,(
t
,
s
)
+
2aik
y,(
t,
s
+
1)
=
yr(
t,
s)
+
2ail+ 2ait
+
+(
t
,
s)
(B .12)
where
k,l
are integers, constant over all of
V,
because of the
continuity of
yr,
and where
I$(t,s)l
-
<
2-
IC,(
2,
s
I
provided
I+(?,
s)
I
IG,(t,
s)1/2.
For this
it
is sufficient (see
(B.6))
to impose r
I
a/(4rb),
which we can do without loss of the
previous estimates. One finds then
14(t,s)[Il,
forall(t,s)EV.
By
construction
V
is a neighborhood of
[0,1l2.
In particular
(B.12)
is valid on
[0,1]*,
which is enough to again lead to a
contradiction. We have
0
=
~r(
191)
-
Yr(1,O)
+
~r(1,O)
-
rr(O,O)
+Y,(O,O)-Y~(O,~)+Y,(O,~)-Y,(~,~)
=
2ail+ 2ai
+
4(
1,O)
+
2rik
-
2ail-
4(
0,O)
-
2aik
=2ai+4(1,0)-4(O,O)
#O
since
I
4(1>0)
13
I4(0,0)
Is
1.
This contradiction concludes the proof.
APPENDIX
C
PROOF
OF
THE
THEOREMS
IN
SECTION
111-B-3
Proof
of
Theorems
2.5,
2.6:
Using the Poisson formula
2a (x-;k)
I€Z
=
a
ktL
=
we find
0
integral over
x,
and once on the sum over k),
C
I(gmn,f>I*
m.n
The decay condition
(2.3.13)
on
P
implies that the sum over
k
always converges. It also implies that this sum tends to zero for
pO
+
0,
so
that the coefficient of
II
f
11'
in
(C.1)
is strictly positive
for small enough
po.
On the other hand, we also have
m,n
(C.2)
for all
po
>
0.
Together, the lower and upper bounds
(C.1)
and
(C.2)
imply that
P:
>
0,
with
Pi
=
inf
(
pol
the
g,,
associated to
g,
pO,
q0
do not constitute a frame).
This proves Theorem
2.5.
The inequalities
(C.l)
and
((2.2)
also
immediately prove Theorem
2.6.
0
The proofs of Theorems
2.7
and
2.8
are very similar.
Proofs of Theorems
2.7
and
2.8:
One uses the unitarity of
the Fourier transform to write
Hence, separating the sum over
k
into the term for
k
=
0
and a
sum over
k
#
0,
and applying Cauchy-Schwarz (once on the
As
in the proof of Theorem
2.5,
this can be rewritten with the
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
loo0
IEEE
TRANSACTIONS
ON
INFORMATION
THEORY,
VOL.
36,
NO.
5,
SEPTEMBER
1990
help of the Poisson formula,
into (C.51, and defining
m"= m
-
m',
one finds
The same arguments as in the proofs of Theorems
2.5
and 2.6
then lead
to
the desired conclusions.
0
Applying Cauchy-Schwarz twice, in the second term (once on
0
estimates
(2.3.25)
and
(2.3.26).
In
the
where
'
=lw+?
and
the
frame
Ih;n
Im,n
the sum over
m",
and Once on the integral Over
x)
leads to the
E
z)
is used (see Section
II-C-za)),
one has to be a little more
careful. The equivalent of (C.1) is then
b,
<
2.
In the computation of
PI,
it
is sufficient to take the supre-
mum over
x
E
[2ir/3, 4ir/3]. For
x
in this interval, and for
Proof of Theorem
2.10:
For
b,,
=
1,
the
$mn;l
are
Y.
Meyer's
basis. We start by showing that the
$m,n:bll
still constitute a
frame for
6,
in a neighborhood of
1.
For
b,
=
2, the
$mn;z
=
$m
2n:
do not span
L'(R).
We therefore restrict our attention to
with
Is1
2
2irb;'
2
ir, one finds that only the couples
(m, m')
E
{(
-
2,2),
(
-
1,1),(
-
1,2),
(O,O),(O,
11,
(1,O))
lead to nonzero con-
tributions to
P,.
As the supremum of the sum of a finite number
112
of continuous -functions,
-PI
is therefore continuous. On the
other hand, since support
$
c
[
-
8ir/3,8ir
/3],
one finds that
P,(s)=
0
if
Is1
2
16ir/3. For
b,
<
2, this implies that only the
choices
1
=
0,
1 or 2 lead to nonzero contributions in the sums
(2.3.251, (2.3.26). This implies that the right hand sides of
(2.3.251, (2.3.26) are continuous in
b(].
For
bo=
1 these two
expressions are equal to
1.
By continuity we find therefore that
(2.3.25)
>
0
and (2.3.26)
<
m
on a neighborhood of
b,
=
1.
I
r
I
I
fi
[
/6".
lfi(
U
rx
)
I
I
fi
(
arx
+
k
)
I
I
f
(
x
)
1'1
(
kfO
To
show that the
$mn;bll
constitute a basis, we introduce the
operator
S(bO)
=
$mn;bl,($mn;l~
'>.
+
[
kxdu
lk(
urx>
I
I
fi
(arx
+
2
k
)
1
I
f(
-
x)
1'1
'I2
m
m,n
In the terminology of Section 11-A, we can write
S(b")
=
T(bn)*T(l)
where T(b,,), T(1) are the frame operators for the frames
$mn;bll,
$mn;l
respectively.
To
prove that the
$mn;bll
constitute a
basis, it is sufficient to prove that
S(b,,)
is one-to-one and onto,
since
S(b,)$mn;l
=
$mn;bll.
Since T(1) is unitary, and T(bO)* is
S(b,)
is one-to-one. We have
This leads again to the same bounds (2.3.231, (2.3.24).
proof
of
Theorem
2.9:
Applying the Poisson formula gives
Onto (see Proposition
we
Only
need
to
prove
that
T(b(l)*
Or
Any
kEZ,
k#O
can be decomposed, in a unique way, as
k
=
2"'k',
where
m',
k'
E
Z,
m'
2
0
and
k'
odd. Substituting this
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE WAVELET TRANSFORM, TIME-FREQUENCY LOCALIZATION AND SIGNAL ANALYSIS
1001
Since support
4
=[-8a/3, -2a/31~[2a/3,8a/3],
and
a,,
=
2,
($m,,;bl,,4)
=
0
for Iml
>
1.
One checks easily, using
I+(X)I<C,(l+/x12)-N
that
C
l(+mn;~,l~+)l
fl€Z
converges, and is continuous in
b,,
for m=0,
kl.
Hence the
coefficient
of
11
f
in the right-hand side of
(C.6)
is continuous
in
b,.
Since this coefficient is equal to
1
for
b,,
=
1,
it is
therefore strictly positive on a neighborhood of
b,,
=
1.
This
implies that, on that neighborhood,
S(b,,)
is one-to-one. This
concludes the proof.
0
APPENDIX
D
PROOFS
OF
THE
THEOREMS
IN
SECTION
111
Proof of Theorem
3.1:
Since the g,, constitute a frame,
with dual frame
imn,
we have, for all
fl,
f2
E
L2(R),
(f27fl>=
C
(f2,imnJl).
m.n
E
Z
Fix T,
a
>
0.
For
t,
o
>
0
we define
constitute frames, with frame constants
A,
E
and
I?-',
A-',
respectively. Similar to the proof of Theorem
2.5
we use the
Poisson formula to estimate the last two terms in
(D.1).
This
leads to
Inq,,lT
+
I
l€H
From the conditions on g, we have
(D.2)<:C2
SUP
[I+(x-nq,)2]-a
/"4,]1>
T
+
I
I
E
Z
1x1
5
7-
27r
lx
-
-/I
5
T
PI1
-a
[l+(x-nq,--~l)']
.
(D.3)
The contribution for
n
>
(T
+
t)/q,
is exactly equal to that for
n
<
-(T
+
t)/q,,
so
that we may restrict ourselves to negative
n,
at the price of a factor
2.
By redefining
y
=
x
-(2a/p0)1
if
1
is positive, we see that we may restrict ourselves
to
negative
1
as
well. Hence
(D.3)<4C2
sup
[l+(~+nq,)~]-~
"q">T+lI20
lxl5T
27r
lx
-
--I1
I
T
P
I1
-a
,
[
1
+
(nq,
-
T
+
However, for any
a,
b
>
0,
we have
[l+(a+bf)y
I20
5(1+
a2)-a
+
$iX(l+*2)-Q
<
1+22.-lb-'(l+-)](1+a') 1
-[
2a-1
-
a
+
1/2
9
where we have used the fact that the
g,,,
and the
i,,,
both
if
a
>
1/2.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
1002
IEEE
TRANSACTIONS ON
INFORMATION
THEORY, VOL.
36,
NO.
5,
SEPTEMBER
1990
Consequently
One then has (see the proof of Theorem
3.1)
P(2a
-
1)
-2a
+
1/2
-
<
sup
c
I
(
fl>
(h,,,,
1-
)
I
.
c
[1+(nqo-T)2]
nqo
>
T
+
I
llfll=
I
nEZ
m
<
ml,
or
m
>
ml
A
similar argument shows that, for
t
2
2qo,
nqo
>
T
+
f
-2a
+
1
2-"[l+(t-2q(1)2]
.
+
I
(hmn
(
1
-
pri,
+
pfi,)f)
I]
+
SUP
I<fl>(hmn)->l
llflll
=
1
mll
sin
s
ml
lnhlll
z
a(l'"T
+
I
We find therefore that there exists a constant
~(p~),q~)),
inde-
pendent
of
T
or
t,
such that
I
1
\
1/2
I
+
K(q0,Po)1/2(1+
~2)-'a+1/2]11fll},
(D.5)
since
(1
+
t2)-2a+1,
(1
+
w~)-'~+'
0
for
t,w
+
0,
this proves
+
B-
I/2
[
mII
s
m
s
ml
I(hmn9QTf);l)).
(D.8)
the theorem.
0
Inbol
z
ac'"T
+
I
Remark:
The estimates in this proof cause
t,,
U,,
when calcu-
lated using
(DS),
to be much larger for a given
E,
and e.g., for
Gaussian
g,
than observed in numerical calculations. The inter-
mediate estimate
(D.2)
leads to much better values of
t,
(a
One has
similar formula can of course be written for
Pflf,
leading to
estimates for
we).
If we define
>
ml
<
I(hmn,(~~i,-~~,l)f)12
nEZ
m
2P
-
<-
c
dY
5
*
(t
;
Y
=
SUP
c
I
dx
*
W")
I
I
g(x
-
Y
*
W")
I
then
~(p,,,
qo)1/2,
in the estimate
(DS),
can be replaced by
+x>r
n=O
6"
m
>
ml
orm
<
m,,L,is
lyl
s
a1
/Eh
277
bo
*(x
-
y)>
f
all
5
ly
-
a["'-/ls
a,
The same thing can be done for
K(qo,
po)'/2.
Proof
of
Theorem
3.2:
We define the set
B,
as
B,(T,R,,R,)
=
((m,n);
mo
I
m
I
ml, In6,,l
I
a;"'T+
t)
(D.7)
where
mo,
MI,
and
t,
to be defined next, depend on
no,
n,,
and
E.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES: THE
WAVELET TRANSFORM,
TIME-FREOUENCY
LOCALIZATION
AND
SIGNAL
ANALYSIS
1003
where we have used that, for all
x
E
R,
(1+
x’)[l+(x
-S)’]4(S)
2
1
with
4
defined by
If we choose
1
<
K
<
a,
then
l€Z
and
Using the same techniques as in the proof
of
Lemma
2.2,
one
finds, for
RI,
I
lyl,
[
a;”lfl,]-2‘*
-
K)
1
1
I----
In
a,
2(a
-
K)
where we have assumed that
m,
2
(In
P
-
In
(a
-
K)
-
In R,)/ln
a(,.
Similarly, for
lyl
I
RI,
provided
m,,
I
(In
p
-
In(a
-
K)-
In R,,)/ln
a,,.
It is clear from
this that, for
a,,,
RI,
E
given, we can choose
mu,
mI
so
that
(D.lO)
Since
y
>
1/2,
this converges. It is moreover clear that
t
can be
chosen
so
that the coefficient of
llf1I2
in (D.10) is smaller than
Be2/4(rn1
-
m,,
+
l), i.e., such that
l(hm,,QTf)l2
I
Be2/411f1I2.
(D.11)
m,lsmsml
b,,lnl>
armT
+
f
The statement
(3.6)
now
follows directly from (D.81, (D.9) and
(D.11).
U
REFERENCES
D. Gabor, “Theory of communication,”
J.
Inst. Elect. Eng.
(London),
vol.
93, no.
111,
pp. 429-457, 1946.
M. J. Bastiaans, “Gabor’s signal expansion and degrees
of
free-
dom of a signal,”
Proc. IEEE,
vol.
68, pp. 538-539, 1980.
-,
“A sampling theorem for the complex spectrogram and
Gabor’s expansion
of
a signal in Gaussian elementary signals,”
Optical Eng.,
vol.
20, pp. 594-598, 1981.
A.
J. E. M. Janssen, “Gabor representation of generalized func-
tions,”
J.
Math. Appl.,
vol. 80, pp. 377-394, 1981.
~,
“Gabor representation and Wigner distribution of signals,”
in
Proc. IEEE,
1984, pp. 41.B.2.1-41.B.2.4.
M.
J.
Davis and E.
J.
Heller,
J.
Chem.
Phys.,
vol.
71, pp. 3383-3395,
1979.
J.
R. Klauder and E. Sudarshan,
Fundamentals
of
Quantum Optics,
New York: Benjamin, 1968.
R.
J. Glauber, “The quantum theory of coherence,”
Phys. Rec.,
vol.
130, pp. 2529-2539, 1963; “Coherent and incoherent states of
the radiation field,”
Phys. Rev.,
vol.
131, pp. 2766-2788, 1963.
J.
R. Klauder and B.-S. Skagerstam, “Coherent states,” Singa-
pore: World Scientific, 1985.
E.
Lieb, “Thomas-Fermi theory and related theories of atoms and
molecules,”
Re[,. Mod. Phys.,
vol.
53, pp. 603-641, 1981.
G.
A. Hagedorn, “Semiclassical quantum mechanics
I:
The
ii
0
limit for coherent states,”
Comm. Math. Phys.,
vol.
71, pp. 77-93,
1980.
C.
W. Helstrom, “An expansion
of
a signal in Gaussian elemen-
tary signals,”
IEEE Trans.
Inform.
Theory,
vol.
12, pp. 81-82, 1966.
N.
G. de Bruijn, “Uncertainty principles in Fourier analysis,” in
Inequalities,
0.
Shisha, Ed. New York: Academic Press, pp.
T. A. C. M. Claassen and W. F.
G.
Mecklenbrauker. “The Wigner
distribution-A tool for time-frequency signal analysis,”
Philips
J.
Res.,
vol. 35, pp. 217-250, 276-300, 372-389, 1980.
C. P. Janse and A. J. M. Kaiser, “Time-frequency distributions of
loudspeakers: The application of the Wigner distribution,”
J.
Audio Eng. Soc.,
vol. 31, pp. 198-223, 1983.
R.
J.
Duffin and A. C. Schaeffer, “A class of nonharmonic Fourier
series,”
Trans. Am. Math. Soc.,
vol. 72, pp. 341-366, 1952.
57-71, 1967.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
R. M. Young,
An Introduction to Nonharmonic Fourier Series.
New York: Academic Press, 1980.
1.
Daubechies, A. Grossmann, and
Y.
Meyer, “Painless non-
orthogonal expansions,”
J.
Math. Phys.,
vol. 27, pp. 1271-1283,
1986.
A. Grossmann and J. Morlet, “Decomposition of Hardy functions
ito square integrable wavelets of constant shape,”
SIAM
J.
Math.
Anal.,
vol. 15, pp. 723-736, 1984.
P. Goupillaud, A. Grossmann, and J. Morlet, “Cycle-octave and
related transforms
in
seismic signal analysis,”
Geoaploration,
vol.
23, p.
85,
1984.
A. Grossmann, J. Morlet, and T. Paul, “Transforms associated to
square integrable group representations,”
J.
Math. Phys.,
vol. 26,
pp. 2473-2479, 1985;
Ann. Inst. Henri Poincare‘,
vol. 45, 293-309,
1986.
E.
W. Aslaksen and J. R. Klauder, “Unitary representations of the
affine group,”
J.
Math. Phys.,
vol. 9, pp. 206-211, 1968; “Continu-
ous representation theory using the affine group,”
J.
Math. Phys.,
T. Paul, “Functions analytic on the half-plane as quantum me-
chanical states,”
J.
Math. Phys.,
vol. 25, pp. 3252-3263, 1984.
-,
“Affine coherent states and the radial Schrodinger equa-
tion.
I.
Radial harmonic oscillator and hydrogen atom,” to be
published.
C. Fefferman and
R.
de la Llave, “Relativistic stability of matter,”
Rep. Math. Iberoamericana,
vol. 2, pp. 119-213, 1986.
I.
Daubechies, “Time-frequency localization operators-A geo-
metric phase space approach,”
IEEE Trans. Inform. Theory,
vol.
34, pp. 605-612, 1988.
I.
Daubechies and
T.
Paul, “Time-frequency localization operators
-A geometric phase space approach
11.
The use of dilations,”
Ini,erse Problems,
vol. 4, pp. 661-680, 1988.
J. Morlet, G. Arens,
I.
Fourgeau, and D. Giard, “Wave propaga-
tion and sampling theory,”
Geophys.,
vol. 47, pp. 203-236, 1982;
“Sampling theory and wave propagation,” NATO AS1 Series, vol.
1,
Issues in Acoustic Signal /Image Processing and Recognition,
C. H. Chen, Ed. Berlin: Springer, pp. 233-261.
R. Kronland-Martinet, J. Morlet, and A. Grossmann, “Analysis of
sound patterns through wavelet transforms,” preprint CTP-87/p.
1981, Centre de Physique Thtorique, CNRS, Marseille, France,
1987.
A. Grossmann, “Wavelet transforms and edge detection,” to be
published
in
Stochastic Processes in Physics and Engineering,
Ph.
Blanchard, L. Streit, and M. Hasewinkel, Eds.
A. Grossmann, M. Holschneider, R. Kronland-Martinet, and J.
Morlet, “Detection of abrupt changes
in
sound signals with the
help of wavelet transforms,” in
Inrerse Problems: An Interdisci-
plinary Study, Adimces in Electronics and Electron Physics,
Supp.
19. New York: Academic, 1987.
S.
Mallat, “A theory for multiresolution signal decomposition,”
Ph.D. thesis, Univ. of Pennsylvania, Depts. of Elect. Eng. and
Comput. Sci., 1988.
A. Grossmann and J. Morlet, “Decomposition of functions into
wavelets of constant shape and related transforms,” in
Mathemat-
ics and Physics, Lectures
on
Recent Results.
Singapore: World
Scientific, 1985.
Y. Meyer, “Principe d’incertitude, bases hilbertiennes et algkbres
d’opkrateurs,”
Se‘minaire Bourbaki,
nr. 662, 1985-1986.
P.
G.
LemariC and
Y.
Meyer, “Ondelettes et bases hilbertinennes,”
Rei.. Math. Iberoamericana,
vol. 2, pp. 1-18, 1986.
G. Battle, “A block spin construction of ondelettes. Part
I:
LemariC
functions,”
Comm. Math. Phys.,
vol. 110, pp. 601-615, 1987.
P. G. LemariC, “Une nouvelle base d’ondelettes de
L2(Rn),’’
to be
published
in
J.
de Math. Pures et Appl.
a) Ph. Tchamitchian, “Calcul symbolique sur les
o
Crateurs de
Acad. Sc. Paris, vol. 303, strie
I,
pp. 215-218, 1986; b) Ph.
Tchamitchian, “BiorthogonalitC et thCorie des opkrateurs,” to be
published
in
Rei.. Math. Iberoamericana.
S.
Mallat, “Multiresolution approximation and wavelets,”
Trans.
Am. Math. Soc.,
vol. 135, pp. 69-88, 1989.
Y.
Meyer, “Ondelettes, function splines, et analyses graduies,”
Univ. of Torino, 1986.
S.
Mallat, “A Theory for multiresolution signal decomposition:
The wavelet representation.”
IEEE Trans. Pattern Anal. Machine
Intell.,
vol. 31, pp. 674-693, 1989.
vol.
10,
pp. 2267-2275, 1969.
CaldCron-Zygmund et bases inconditionnelles de
L
P
(R“),”
C. R.
1.
Daubechies, “Orthonormal basis of compactly supported
wavelets,”
Comm. Pure Applied Math.,
vol. 41, pp. 909-996, 1988.
S.
G. Mallat, “Multifrequency channel decompositions
of
images
and wavelet models,”
IEEE
Trans. Acoust. Speech Signal Process-
ing,
vol. 37, no. 12, pp. 2091-2110, Dec. 1987.
G.
Battle and P. Federbush, “Ondelettes and phase cell cluster
expansions: A vindication,”
Comm. Math. Phys.,
1987.
I.
Daubechies, “Discrete sets of coherent states and their use in
signal analysis,” in
Proc.
1986
Int. Conf. Diff. Equations Math.
Phys.,
Birmingham, AL, Springer Lecture Notes
in
Mathematics
nr. 128.5, pp. 73-82.
1.
Daubechies and T. Paul,
Wavelets-Some applications,”
Proc.
Int. Conf. Math. Phys.,
M. Mebkhout and R. SCnCor, Eds. Singa-
pore: World Scientific, 1987.
I.
Daubechies, “How to frame Bargmann and Hardy-Frame
bounds for Hilbert spaces
of
entire functions,” unpublished mem-
orandom, AT&T Bell Laboratories, 1987.
I.
Daubechies and A. Grossmann, “Frames of entire functions in
the Bargmann space,”
Comm. Pure Appl. Math.,
vol. 41, pp.
151-164, 1988.
R. R. Coifman and R. Rochberg, “Representation theorems for
holomorphic and harmonic functions in
L”,” Aste‘risque,
vol. 77,
S.
Janson, J. Peetre, and R. Rochberg, “Hankel forms and the
Fock space,” Uppsala Univ., Math. report, 1986.
H. G. Feichtinger and K. Grochenig, “A unified approach to
atomic decompositions via integrable group representations,” in
Proc. Function Spaces Applications,
Lund, 1986, to appear in
Springer Lect. Notes in Math.
no. 1302, pp. 52-73; “Banach spaces
related to integrable group representations and their atomic de-
composition
I,
11,
and
111,”
to be published,
J.
Funct. Anal.,
vol.
83, 1989.
M.
Rieffel, “Von Neumann algebras associated with pairs of
lattices in Lie groups,”
Math. Ann.,
vol. 257, pp. 403-418, 1981.
G. Kaiser, “A sampling theorem for signals in the joint time-
frequency domain,” to be published.
R. Balian, “Un principe d’incertitude fort en thCorie du signal on
en mCcanique quantique,” C. R. Acad. Sc. Paris, vol. 292, sCrie 2,
1981.
F. Low, “Complete sets of wave-packets,’’
in
A Passion for Physics
-Essays in Honor of Geofiey Chew,”
pp. 17-22. Singapore:
World Scientific, 1985.
H. Elbrond Jensen, T. Hoholdt, and J. Justesen, “Double series
representation of bounded signals,”
IEEE Trans. Inform. Theory,
vol. 34, pp. 613-624, 1988.
J. Zak, “Finite translations in solid state physics.”
Phys. Rei.. Lett.,
vol. 19, pp. 1385-1397, 1967; “Dynamics of electrons in solids in
external fields,”
Phys. Rer.,
vol.
168,
pp. 686-695; “The kq-repre-
sentation in the dynamics of electrons
in
solids,”
Solid State Phys.,
W. Schempp, “Radar ambiguity functions, the Heinsenberg group,
and holomorphic theta series,’’
Proc. of the Am. Math. Soc.,
vol.
92, 1984.
M. Reed and B. Simon,
Methods and Modem Mathematical Physics.
IVAnalysis of Operators.
M. Boon, J. Zak, and J. Zucker, “Rational von Neumann lattices,”
J.
Math. Phys.,
vol. 24, pp. 316-323, 1983.
J. Zak, “Lattice operators in crystals for Bravais and reciprocal
vectors,”
Phys. Rei,.,
vol. B 12, pp. 3023-3026, 1975.
A. J.
E.
M. Janssen, “Bargmann transform, Zak transform, and
coherent states,”
J,
Math. Phys.,
vol. 23, pp. 720-731, 1982.
A. J. E. M. Janssen, “The Zak transform: A signal transform for
sampled time-continuous signals,”
Philips
J.
Res.,
vol. 42, 1987.
V.
Bargmann, P. Butera, L. Girardello, and J. R. Klauder, “On
the completeness of coherent states,”
Rep. Math. Phys.,
vol. 2, pp.
221-228, 1971.
A.
M. Perelomov, “Note on the completeness
of
systems of
coherent states,”
Teor. i. Matem. Fis.,
vol.
6,
pp. 213-224, 1971.
H. Bacry, A. Grossmann, and J. Zak, “Proof of the completeness
of lattice states
in
the kq-representation,”
Phys. Rei,.,
vol. B 12,
pp. 1118-1120, 1975.
M. Reed and B. Simon,
Methods of Modem Mathematical Physics,
11.
Fourier Analysis and Self-Adjointness.
New York: Academic
Press, 1975.
D. Slepian and H.
0.
Pollak, “Prolate spheroidal wave functions,
Fourier analysis and uncertainty,”
I,
Bell. Syst. Tech.
J.,
vol. 40,
pp. 11-66, 1980.
vol. 27, pp. 1-62, 1972.
New York: Academic Press, 1978.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.
DAUBECHIES:
THE
WAVELET
TRANSFORM, TIME-FREQUENCY
LOCALIZATION
AND
SIGNAL ANALYSIS
1005
pp. 43-64, 1961; H.
J.
Landau and
H.
0.
Pollak,
11,
Bell. Syst.
Techn.
J.,
vol. 40, pp. 65-84, 1961; H.
J.
Landau and H.
0.
Pollak,
111,
Bell. Syst. Techn.
J.,
vol. 41, pp. 1295-1336, 1962.
[66]
D.
Slepian, “On bandwidth,” Proc.
IEEE,
vol.
64, pp. 292-300,
1976.
[67] A. Anntodo, G. Grasseau, and
M.
Holschneider, “Wavelet trans-
form analysis of invariant measures
for some dynamical systems,”
Phys. Rec. Le??.,
vol.
61, pp. 2281-2287, 1988.
[681 J. Ville, “Thtorie et applications de la notion de signal analytique,”
Recue Cables et Transmissions,
vol. 1, pp. 61-74, 1948.
1691 G. Battle, “Heisenberg proof of the Balian-low theorem,”
Lett.
Math. Phys.,
vol. 15, pp. 175-177, 1988.
[70]
I.
Daubechies and A.
J.
E.
M.
Janssen, “Two theorems on lattice
expansions,” submitted for publication.
[711 H. Landau, “On the density
of
phase space functions,” submitted
for publication.
Authorized licensed use limited to: STATE UNIV NY BINGHAMTON. Downloaded on March 11,2024 at 16:52:51 UTC from IEEE Xplore. Restrictions apply.